hust校赛d题 PHP is the best language int the world(二分图着色+递推)-php教程-PHP中文网

题目大意是给出一个图，要求判断是否是二分图，如果是，求二分图两个节点集之差的最小值。

两个人如果不会争吵的话连一条边，形成一个图，取这个图的反图。这个反图之间存在边则

说明这两个人不能在同一个team。首先二分染色看是否能够将反图变成一个二分图。

如果能染成二分图，记录每个二分图颜色人数。在某个联通分量里白色/黑色可以交换。

接下来用dp[i][j] = 1表示前i个联通分量能够形成一个人数为j的team.

然后在dp[num][s]里面遍历找到相差最小的team分法，输出答案，num为联通分量数。

代码如下：

#include  #include  #include  #include  #include  #include  #include  #include  #include  #include #include#include #includeusing namespace std;  #define LL long long  const int maxn = 100 + 5;const int INF = 1000000000;int color[maxn];//vector G[maxn];int G[maxn][maxn];int one, two, num[maxn][2], n;int d[maxn][maxn];bool bipartite(int u) {                       //判断节点u所在的联通分量是否为二分图 	if(color[u] == 1) one++;	else two++;	for(int v = 1; v <= n; v++) {		if(G[u][v] && u != v) {			if(color[u] == color[v]) return false;			if(!color[v]) {				color[v] = 3 - color[u];				if(!bipartite(v)) return false; 			}		}	}	return true;} int main() {	freopen("input.txt", "r", stdin);	int t; scanf("%d", &t);	while(t--) {		memset(d, 0, sizeof(d));		memset(color, 0, sizeof(color));		int m; scanf("%d%d", &n, &m);		for(int i = 1; i <= n; i++)			for(int j = 1; j <= n; j++) G[i][j] = 1;		for(int i = 0; i < m; i++) {			int u, v; scanf("%d%d", &u, &v);			if(G[u][v]) G[u][v] = G[v][u] = 0;		}				int cnt = 0, tag = 1;		for(int i = 1; i <=n; i++) {			if(!color[i]) {				one = 0, two = 0;				color[i] = 1;				if(!bipartite(i)) {					tag = 0;					break;				}				num[cnt][0] = one;				num[cnt][1] = two;				cnt++;			} 		}				if(!tag) printf("No solution\n");		else {			for(int i = 0; i < cnt; i++) {				if(i == 0) d[i][num[i][0]] = d[i][num[i][1]] = 1;				else for(int j = 0; j <= n; j++) if(d[i - 1][j]) d[i][j + num[i][0]] = d[i][j + num[i][1]] = 1;			}			int ans = 1;			for(int i = n/2; i; i--) if(d[cnt - 1][i]) {				ans = i;				break;			}			printf("%d\n", ans);		}	}	return 0;}

登录后复制