poj1417 true liars（並查集 + DP）詳解，poj1417liars
這個題做了兩天了。首先用並查集分類是明白的， 不過判斷是否情況唯一剛開始用的是搜索。總是超時。 後來看別人的結題報告， 才恍然大悟判斷唯一得用DP.
題目大意：
一共有p1+p2個人，分成兩組，一組p1個，一組p2個。給出N個條件，格式如下：
x y yes表示x和y分到同一組
x y no表示x和y分到不同組
問分組情況是否唯一，若唯一則按從小到大順序輸出，否則輸出no。保證不存在矛盾條件，但是有可能出現x=y的情況。
題目分析： 題中會給我們一些信息， 告訴我們那些是同一類， 哪些是不同類。 當然剛開始的時候我們無法判斷那一類是好人、壞人。 那麼我們不妨把有關系的點（無論他們的關系是yes還是 no）全歸為一類， 他們有一個相同的父節點。然後用一個數組(relation[])記錄他與父節點的關系（0代表同類， 1代表異類）。當然因為所給的只是一部分信息， 所以有可能無法把所有點歸為一類（例如：1，2 yes 3，4 yes。只表明1,2同類 ， 3,4同類， 1,3的關系並不知道）。那麼不妨設幾個不同的集合（以父節點為劃分標准）每個集合分為兩類 ，與父節點同類（relation[] = 0）, 與父節點不同類（relation[] = 1）。此時我們問題轉變為答案是否唯一。取每個集合中的一種類型，且僅取一種（同類或不同類）。看累計人數得p1的情況是否唯一。
![]()
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
int n, n1, n2, mi, mx, key, flag, a[605][2], vis[605][605][2], ans[605][2], v[605], d[605][605], pre[610], relation[605];
int find(int x)//尋找最根部的父親節點
{
if(pre[x] == x)
return x;
else if(pre[x] != x)
{
int t = pre[x];
pre[x] = find(pre[x]);//邊尋找最根部父親節點，邊更新原父親節點的信息
relation[x] = (relation[t] + relation[x]) % 2;//類似於種類並查集的更新
}
return pre[x];
}
void work(int a, int b, int c)//合並節點
{
int fx = find(a);
int fy = find(b);
if(fx != fy)
{
pre[fx] = fy;
relation[fx] = (relation[a] + relation[b] + c) % 2;
}
}
void dp()
{
int k = 1;
for(int i = mi+1; i <= (n1+n2); i++)
{
if(v[i] == 1)
{
k++;
int t1 = ans[i][0];
int t2 = ans[i][1];
int mx = min(t1, t2);
for(int j = n1; j >= mx; j--)
{
d[k][j] = d[k-1][j-t1] + d[k-1][j-t2];
if(d[k-1][j-t1] == 1 && d[k-1][j-t2] == 0)
{
vis[k][j][0] = i;
vis[k][j][1] = 0;
}
else if(d[k-1][j-t2] == 1 && d[k-1][j-t1] == 0)
{
vis[k][j][0] = i;
vis[k][j][1] = 1;
}
}
}
}
}
int main()
{
while(scanf("%d%d%d", &n, &n1, &n2) != EOF)
{
if(n == 0 && n1 == 0 && n2 == 0)
break;
//初始化所有節點得父節點和relation
for(int i = 1; i <= n1+n2; i++){pre[i] = i; relation[i] = 0;}
for(int i = 1; i <= n; i++)
{
int a, b;
char c[10];
scanf("%d%d%s", &a, &b, &c);
if(strcmp(c, "yes") == 0)
work(a, b, 0);
else if(strcmp(c, "no") == 0)
work(a, b, 1);
}
//這裡注意一下：到這一步，有可能存在一些點的父節點不是最跟的節點
for(int i = 1; i <= n1+n2; i++)
int t = find(i);
memset(v, 0, sizeof(v));
//ans[i][0]表示與最根節點i同類的節點個數， ans[i][1]代表與最根節點i不同類的節點個數
memset(ans, 0, sizeof(ans));
flag = 0;//存儲一共有多少個不同的最跟部的父節點
mi = 10e9;
for(int i = 1; i <= n1+n2; i++)
{
int x = pre[i];
int y = relation[i];
if(x < mi)
mi = x;
ans[x][y]++;
if(v[x] == 0)
{
v[x] = 1;
flag++;
}
}
/*d[i][j]前i個集合中累計人數為j時有多少種可能， vis[i][j][]保存每一個集合選了哪一類， 為最後輸出用。 vis[i][j][0]表示前i個集合中累計人數為j時的最根節點，vis[i][j][1] 表示前i個集合中累計人數為j時，最根節點為vis[i][j][0]時，與根節點的關系*/
memset(d, 0, sizeof(d));
memset(vis, 0, sizeof(vis));
d[1][ans[mi][0]]++; d[1][ans[mi][1]]++;
vis[1][ans[mi][0]][0] = mi;
vis[1][ans[mi][0]][1] = 0;
vis[1][ans[mi][1]][0] = mi;
vis[1][ans[mi][1]][1] = 1;
dp();
if(d[flag][n1] == 1)//如果前flag個集合中累計人數為n1的可能為1時，有唯一解
{
int j = n1;
for(int i = flag; i >= 1; i--)//從後往前推
{
a[i][0] = vis[i][j][0];
a[i][1] = vis[i][j][1];//記錄第i個集合中取得是哪一類（同類0， 不同類1）
j -= ans[a[i][0]][a[i][1]];
}
for(int i = 1; i <= n1+n2; i++)
{
for(int j = 1; j <= flag; j++)
{
int f = pre[i];
int ff = relation[i];
if(f == a[j][0] && ff == a[j][1])
printf("%d\n", i);
}
}
printf("end\n");
}
else
printf("no\n");
}
return 0;
}
View Code
