大学のコンテストの質問 D PHP は世界で最高の言語です (2 部グラフの色付け + 再帰)

質問の主な目的は、グラフを与え、それが二部グラフであるかどうかを判断するように求めることです。そうであれば、二部グラフの 2 つのノード セット間の最小の差を見つけます。

二人が喧嘩しない場合、辺を結んでグラフを作り、このグラフの逆グラフをとります。これらの逆グラフ

の間にエッジが存在するということは、この 2 人が同じチームに所属できないことを意味します。まず、二部染色を使用して、反転画像を二部画像に変換できるかどうかを確認します。

二部グラフに染めることができたら、二部グラフの各色の人数を記録します。ユニコムの一部コンポーネントで白/黒の交換が可能です。

次に、 dp[i][j] = 1 を使用して、最初に接続された i 個のコンポーネントが j 人の人数でチームを形成できることを示します。

次に、 dp[num][s] を走査して、最小の差、答えを出力します。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;} 

??