题目地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4502
思路：
1.将所有不能在一组的两个人连边，二分图染色，若发现染色不成功，则无解。
2.若染色成功，同一连通分量里的黑点与白点无法分为一组，不同连通分量中的点可与其他连通分量中的任一种组合，dp。
3.设dp[i][j]表示前i个连通分量，是否有差值为j的组合（j可正可负，代表A大于B或B大于A）。设同一连通分量i中的两种点数差值为diff[i]，则若dp[i-1][j]==1，则dp[i][j-diff[i]]=1，dp[i][j+diff[i]]=1（即分到AB或BA）。最后判断是否存在最小的abs(j)使得dp[num][j]==1。
4.输出方案，从后向前判断设当前差值为ans，若dp[i-1][ans-diff[i]]==1成立代表将第i个连通分量两种点分为AB两组，同时ans-=diff[i]；若dp[i-1][ans+diff[i]]==1成立代表将第i个连通分量中两种点分为BA两组，同时ans+=diff[i]，记录即可。
#include<cstdio> #include<vector> #include<cstring> #include<iostream> #include<algorithm> #define debug using namespace std; const int maxn=400+50; const int INF=0x3f3f3f3f; vector<int> G[maxn]; int g[maxn][maxn],n,num; int color[maxn],vis[maxn]; vector<int> group[maxn][2]; int d[maxn][maxn],diff[maxn]; void init() { num=0; memset(g,0,sizeof(g)); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); memset(color,-1,sizeof(color)); for(int i=0; i<=n; i++) { G[i].clear(); group[i][0].clear(); group[i][1].clear(); } } int dfs(int u,int num,int id) { color[u]=id; group[num][id].push_back(u); for(int i=0; i<G[u].size(); i++) { int nt=G[u][i]; if(color[u]==color[nt]) return 0; if(!vis[nt]) { vis[nt]=1; if(!dfs(nt,num,id^1)) return 0; } } return 1; } void print(int ans) { int flag; vector<int> term1,term2; for(int i=num; i>=1; i--) { if(d[i-1][ans-diff[i]+2*n]) { flag=0; ans-=diff[i]; } else if(d[i-1][ans+diff[i]+2*n]) { flag=1; ans+=diff[i]; } for(int j=0; j<group[i][flag].size(); j++) { term1.push_back(group[i][flag][j]); } for(int j=0; j<group[i][flag^1].size(); j++) { term2.push_back(group[i][flag^1][j]); } } printf("%d",term1.size()); for(int i=0; i<term1.size(); i++) { printf(" %d",term1[i]); } printf("\n"); printf("%d",term2.size()); for(int i=0; i<term2.size(); i++) { printf(" %d",term2[i]); } printf("\n"); } int main() { #ifdef debu freopen("in.txt","r",stdin); #endif // debug int t,cas=0; scanf("%d",&t); while(t--) { scanf("%d",&n); init(); for(int i=1; i<=n; i++) { int x; while(scanf("%d",&x)!=EOF&&x) g[i][x]=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].push_back(j); } } } int flag=0; for(int i=1; i<=n; i++) { if(!vis[i]) { vis[i]=1; if(!dfs(i,++num,0)) { flag=1; break; } } } if(++cas!=1) printf("\n"); if(flag) printf("No solution\n"); else { d[0][2*n]=1; for(int i=1; i<=num; i++) { diff[i]=group[i][0].size()-group[i][1].size(); for(int j=n; j>=-n; j--) { if(d[i-1][j+2*n]) { d[i][j-diff[i]+2*n]=1; d[i][j+diff[i]+2*n]=1; } } } int minx=INF,Diff; for(int i=-n; i<=n; i++) { if(d[num][i+2*n]&&abs(i)<minx) { minx=abs(i); Diff=i; } } print(Diff); } } return 0; }