poj-1112 (二分图染色+dp分组)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int N=110;
 6 int g[N][N];
 7 int r[N][N];//模型图
 8 int c[N];// 染的颜色
 9 int num[N][2]; int snt; // 联通分量
10 int s[N]; //每个点所属联通分量
11 bool dp[N][N];// 前i个联通分量能否组成为J人的一组
12 int ans[N][N];// 前i个联通分量组成为J人的一组的选择（选择0一组还是1一组）
13 int n;
14 bool flag ; 
15 void dfs (int rt)  {
16     for (int i=1;i<=n;i++) {
17         if (r[rt][i]) {
18             if (c[i]==-1) {
19                 c[i]=c[rt]^1;
20                 num[snt][c[i]]++;
21                 s[i]=snt;
22                 dfs (i);
23                 if (flag) return ;
24             }
25             if (c[i]==c[rt]) {flag=1; return;}
26         }
27     }
28     return ;
29 } 
30 int main ()
31 {
32     ios::sync_with_stdio(false);
33     cin>>n; 
34     for (int i=1;i<=n;i++) {
35         int x;
36         while (cin>>x&&x) g[i][x]=1;
37     }
38     for (int i=1;i<=n;i++)
39         for (int j=1;j<=n;j++) {
40             if (j!=i&&g[j][i]==0)
41                 r[i][j]=r[j][i]=1;（//不相互认识的人建立无向边，这两个人一定在不同的分组，（0，1）染色问题）
42         }
43     memset (c,-1,sizeof (c));
44     for (int i=1;i<=n;i++) {
45         if (c[i]==-1) {
46             c[i]=0;
47             num[++snt][0]++;
48             s[i]=snt;
49            dfs (i);
50             if (flag) {
51                 cout<<"No solution"<<endl;
52                 break;
53             }
54         }
55     }
56     if (!flag) {
57         dp[0][0]=1;
58         for (int i=1;i<=snt;i++)
59             for (int j=n/2;j>=0;j--) {
60                 if (j>=num[i][0]&&dp[i-1][j-num[i][0]])
61                     {dp[i][j]=1; ans[i][j]=0;}
62                 if (j>=num[i][1]&&dp[i-1][j-num[i][1]])
63                     {dp[i][j]=1; ans[i][j]=1;}
64             }
65         int t1;
66         for (int i=n/2;i>=0;i--)  
67             if (dp[snt][i]) {t1=i;break;}
68         int _n=t1; int _s=snt;
69         while (_s) {
70             for (int i=1;i<=n;i++) 
71                 if (s[i]==_s&&c[i]==ans[_s][_n])  c[i]=-1;
72             _n-=num[_s][ans[_s][_n]];
73             _s--;
74         }
75         cout<<n-t1;
76         for (int i=1;i<=n;i++)
77             if (c[i]>=0)  cout<<" "<<i;
78         cout<<endl;  
79         cout<<t1;
80         for (int i=1;i<=n;i++)
81             if (c[i]<0)  cout<<" "<<i;
82         cout<<endl;
83         
84     }
85     return 0;
86 }
抓住青春的尾巴。。。