UVa 1627 - Team them up! (二分图染色 + 01背包)

本文主要是介绍UVa 1627 - Team them up! (二分图染色 + 01背包)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4502

题目大意：

将 \(n\) 个人分成两组，每组的人互相认识，每个人都在一个组中，且每个组中至少有一个人，要求两个组的人数之差尽量小，求分组方案。

题解：

认识的人不一定在同一个组里，但不认识的人一定不在同一个组里，所以可以将不认识的人互相连边，于是转化成二分图判定，如果不是二分图，则该问题无解。

将连通分量染色后，就是该连通分量的分组方案，颜色还可以翻转过来，也就是分组可以互换。这样我们记录一下每个连通分量中两个组的人数差值是多少，在所有连通块中选择出差值绝对值最小的方案。这个问题类似 \(01\) 背包，每个连通块有两个决策，每种决策对应一个“体积”，要求选择体积尽可能小的方案。
设 \(dp[i][j]\) 表示选前 \(i\) 个连通块，两组人数相差 \(j\) 的方案是否可行，转移时再记录一下决策即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 105;
const int INF = 1000000007;

int T, n;
int g[maxn][maxn], G[maxn][maxn], d[2][maxn];
int color[2][maxn], cc[maxn];
int dp[maxn][5*maxn], pre[maxn][5*maxn];
int flag, tot;
vector<int> ttm[2][maxn], a1, a2;

bool dfs(int u, int block, int t){
	if(color[t][u] == 1) {
		++d[t][block];
		ttm[t][block].push_back(u);
	}
	else {
		--d[t][block];
		ttm[t][block].push_back(u);
	}
	for(int v = 1 ; v <= n ; ++v){
		if(G[u][v]){
			if(color[t][v] == color[t][u]) return false;
			if(!color[t][v]){
				color[t][v] = 3 - color[t][u];
				if(!dfs(v, block, t)) return false;
			} 
		}
	}
	return true;
} 

ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }

int main(){
	int f = 0;
	scanf("%d", &T);
	while(T--){
		if(f) printf("\n");
		f = 1;
		flag = 1;
		tot = 0;
		a1.clear(), a2.clear();
		memset(pre, 0, sizeof(pre));
		memset(dp, 0, sizeof(dp)); 
		memset(d, 0, sizeof(d));
		memset(color, 0, sizeof(color));
		memset(cc, 0, sizeof(cc));
		memset(g, 0, sizeof(g));
		memset(G, 0, sizeof(G));
		scanf("%d", &n);
		for(int i = 1 ; i <= n ; ++i) ttm[0][i].clear(), ttm[1][i].clear();
		int u;
		for(int i = 1 ; i <= n ; ++i){
			while(1){
				scanf("%d", &u);
				if(!u) break;
				g[i][u] = 1;
			}
		}
		
		for(int i = 1 ; i <= n ; ++i){
			for(int j = 1 ; j <= n ; ++j){
				if(i == j) continue;
				if(!g[i][j] || !g[j][i]) G[i][j] = G[j][i] = 1; // 不认识的人连边
			}
		}
		
		for(int i = 1 ; i <= n ; ++i){
			if(!color[0][i]){
				color[0][i] = 1;
				++tot;
				if(!dfs(i, tot, 0)){
					printf("No solution\n");
					flag = 0;
					break;
				}
			}
		}
		
		if(flag){
			tot = 0;
			for(int i = 1 ; i <= n ; ++i){
				if(!color[1][i]){
					++tot;
					color[1][i] = 2;
					dfs(i, tot, 1);
				}
			}	
		}
		
		if(flag){ // 有解 
			dp[0][200] = 1;
			for(int i = 1 ; i <= tot ; ++i){
				for(int j = -n ; j <= n ; ++j){
					if(dp[i-1][j-d[0][i]+200]){
						pre[i][j+200] = 1;
						dp[i][j+200] |= dp[i-1][j-d[0][i]+200];	
					}
					if(dp[i-1][j-d[1][i]+200]){
						pre[i][j+200] = 2;
						dp[i][j+200] |= dp[i-1][j-d[1][i]+200];
					}
				}
			}
			
			int ans = INF;
			for(int i = 0 ; i <= n ; ++i){
				if(dp[tot][i+200] == 1){
					ans = i; break;
				}
				if(dp[tot][-i+200] == 1) {
					ans = i; break;
				}
			}
			
			int V = ans;
			for(int i = tot ; i >= 1 ; --i){
				if(pre[i][V+200] == 1){
					V = V - d[0][i];
					cc[i] = 1;
				} else if(pre[i][V+200] == 2){
					V = V - d[1][i];
					cc[i] = 2;
				}
			}
			
			int c1 = 0, c2 = 0;
			for(int i = 1 ; i <= tot ; ++i){
				if(cc[i] == 1){
					for(int j = 0 ; j < ttm[0][i].size(); ++j){
						if(color[0][ttm[0][i][j]] == 1){
							++c1; a1.push_back(ttm[0][i][j]);
						} else{
							++c2; a2.push_back(ttm[0][i][j]);
						}
					}
				} else{
					for(int j = 0 ; j < ttm[1][i].size(); ++j){
						if(color[1][ttm[1][i][j]] == 1){
							++c1; a1.push_back(ttm[1][i][j]);
						} else{
							++c2; a2.push_back(ttm[1][i][j]);
						}
					}					
				}
			}
			printf("%d ", c1);
			for(int i = 0 ; i < a1.size(); ++i){
				printf("%d ", a1[i]);
			} printf("\n");
			printf("%d ", c2);
			for(int i = 0 ; i < a2.size(); ++i){
				printf("%d ", a2[i]);
			} printf("\n");
		}
	}
	return 0;
}

这篇关于UVa 1627 - Team them up! (二分图染色 + 01背包)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！