図論+dp poj 1112 Team Them Up!
5142 ワード
タイトルリンク:
http://poj.org/problem?id=1112
テーマ:
1~nの番号のn人がいて、一人一人の知っている人の番号を与えて、AがBを知っていることに注意して、Bは必ずしもAを知っているとは限らないことに注意して、あなたにすべての人を2つのグループに分けて、各グループの人が互いに認識することを要求して、しかも2つのグループの人数はできるだけ接近します.
各グループの人の番号を求める.
問題解決の考え方:
図論+リュックサック(出力品).
相互認識の関係はグループを確定するのがよくなくて、もし構想を転換して、相互に認識しない情況を考えるのは簡単でずっと多くて、もしAがBを認識しないならば、しかもBはCを認識しないならば、AとCは同じグループに分けなければなりません.そこで、連通成分の染色は、隣接する2つの異なる色(0または1)を染め、それぞれの連通成分を2つのグループに分け、同じ色の人は辺(必ず互いに認識しなければならない)を持つことができず、異なる連通成分を知っている人は必ず互いに認識し、否は連通していると考えられる.
そして問題は複数の連通成分があり、各連通成分には2つのグループがあり、各グループは1つのチームに属しなければならず、2つのチームの人数差が最小であることを求め、それぞれ2つのチームの人を出力しなければならない.
dp[i][j]は、i番目の連通成分を表し、1番目のチームの人数がjの場合に適切に揃えることができるかどうかを示す.
ans[i][j]は状態dp[i][j]に対応する場合の選択を表し、0は0色を選択したノードを表し、1は1色を選択したノードを表す.
dp[num][]を求めた後、ans[num][]の値に基づいて前に押し、色を選んでその色ノードをすべてこのチームに加える.
コード:
http://poj.org/problem?id=1112
テーマ:
1~nの番号のn人がいて、一人一人の知っている人の番号を与えて、AがBを知っていることに注意して、Bは必ずしもAを知っているとは限らないことに注意して、あなたにすべての人を2つのグループに分けて、各グループの人が互いに認識することを要求して、しかも2つのグループの人数はできるだけ接近します.
各グループの人の番号を求める.
問題解決の考え方:
図論+リュックサック(出力品).
相互認識の関係はグループを確定するのがよくなくて、もし構想を転換して、相互に認識しない情況を考えるのは簡単でずっと多くて、もしAがBを認識しないならば、しかもBはCを認識しないならば、AとCは同じグループに分けなければなりません.そこで、連通成分の染色は、隣接する2つの異なる色(0または1)を染め、それぞれの連通成分を2つのグループに分け、同じ色の人は辺(必ず互いに認識しなければならない)を持つことができず、異なる連通成分を知っている人は必ず互いに認識し、否は連通していると考えられる.
そして問題は複数の連通成分があり、各連通成分には2つのグループがあり、各グループは1つのチームに属しなければならず、2つのチームの人数差が最小であることを求め、それぞれ2つのチームの人を出力しなければならない.
dp[i][j]は、i番目の連通成分を表し、1番目のチームの人数がjの場合に適切に揃えることができるかどうかを示す.
ans[i][j]は状態dp[i][j]に対応する場合の選択を表し、0は0色を選択したノードを表し、1は1色を選択したノードを表す.
dp[num][]を求めた後、ans[num][]の値に基づいて前に押し、色を選んでその色ノードをすべてこのチームに加える.
コード:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
// , ,
// , , , ,
#define Maxn 110
struct Node
{
int cnt[2];
int sa[2][Maxn]; //
}node[Maxn];
bool kn[Maxn][Maxn],nn[Maxn][Maxn];
bool vis[Maxn];
int n,num;
bool dp[Maxn][Maxn]; //dp[i] team
int ans[Maxn][Maxn]; // i j
int aa[Maxn],bb[Maxn];//aa ,
void dfs(int v,int p)
{
node[num].cnt[p]++; //
node[num].sa[p][node[num].cnt[p]]=v;//
for(int i=1;i<=n;i++)
{
if(!nn[v][i]||vis[i])
continue;
vis[i]=true;
dfs(i,p^1);
}
}
bool ok() //
{
for(int i=1;i<=num;i++)
{
for(int p=0;p<2;p++)
{
for(int k=1;k<=node[i].cnt[p];k++)
for(int m=k+1;m<=node[i].cnt[p];m++)
{
int a=node[i].sa[p][k],b=node[i].sa[p][m];
if(nn[a][b]) // ,
return false;
}
}
}
return true;
}
int main()
{
int a;
while(~scanf("%d",&n))
{
memset(kn,false,sizeof(kn));
memset(nn,false,sizeof(nn));
for(int i=1;i<=n;i++)
while(scanf("%d",&a)&&a)
kn[i][a]=true;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!kn[i][j]||!kn[j][i])
nn[i][j]=nn[j][i]=true; //
memset(vis,false,sizeof(vis));
num=0; //num
for(int i=1;i<=n;i++) //
if(!vis[i])
{
num++;
vis[i]=true;
node[num].cnt[0]=node[num].cnt[1]=0;
dfs(i,0);
}
if(!ok())
{
printf("No solution
");
continue;
}
memset(dp,false,sizeof(dp));
memset(ans,0,sizeof(ans));
dp[0][0]=true;
for(int i=1;i<=num;i++) // ,
{
for(int j=n;j>=min(node[i].cnt[0],node[i].cnt[1]);j--) //
{
if(!dp[i][j]&&j>=node[i].cnt[0]&&dp[i-1][j-node[i].cnt[0]])
dp[i][j]=true,ans[i][j]=0;
if(!dp[i][j]&&j>=node[i].cnt[1]&&dp[i-1][j-node[i].cnt[1]])
dp[i][j]=true,ans[i][j]=1;
}
}
int gap=n,temp1=0,temp2=0;
for(int i=1;i<=n;i++) //
if(dp[num][i]&&abs(i-(n-i))<gap)
gap=abs(i-(n-i)),temp1=i;
temp2=n-temp1;
if(!temp1||!temp2)
printf("No solution
");
else
{
//printf("%d %d
",temp1,temp2);
int p=0,q=0;
for(int i=num;i>=1;i--)
{
//printf(":::%d
",ans[i][temp1]);
if(ans[i][temp1]) // , 1
{
for(int j=1;j<=node[i].cnt[1];j++)
aa[++p]=node[i].sa[1][j];
for(int j=1;j<=node[i].cnt[0];j++)
bb[++q]=node[i].sa[0][j];
temp1-=node[i].cnt[1]; // ,
} // 0
else
{
for(int j=1;j<=node[i].cnt[0];j++)
aa[++p]=node[i].sa[0][j];
for(int j=1;j<=node[i].cnt[1];j++)
bb[++q]=node[i].sa[1][j];
temp1-=node[i].cnt[0];
}
}
printf("%d",q);
for(int i=1;i<=q;i++)
printf(" %d",bb[i]);
putchar('
');
printf("%d",p);
for(int i=1;i<=p;i++)
printf(" %d",aa[i]);
putchar('
');
}
}
return 0;
}