题目大意是给出一个图，要求判断是否是二分图，如果是，求二分图两个节点集之差的最小值。
两个人如果不会争吵的话连一条边，形成一个图，取这个图的反图。这个反图之间存在边则
说明这两个人不能在同一个team。首先二分染色看是否能够将反图变成一个二分图。
如果能染成二分图，记录每个二分图颜色人数。在某个联通分量里白色/黑色可以交换。
接下来用dp[i][j] = 1表示前i个联通分量能够形成一个人数为j的team.
立即学习“PHP免费学习笔记（深入）”；
然后在dp[num][s]里面遍历找到相差最小的team分法，输出答案，num为联通分量数。
代码如下：
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> #include<set>using namespace std; #define LL long long const int maxn = 100 + 5;const int INF = 1000000000;int color[maxn];//vector<int> 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;} ??
PHP怎么学习？PHP怎么入门？PHP在哪学？PHP怎么学才快？不用担心，这里为大家提供了PHP速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
983
收藏
