poj1417 true liars(并查集 + DP)详解

这个题做了两天了。首先用并查集分类是明白的, 不过判断是否情况唯一刚开始用的是搜索。总是超时。 后来看别人的结题报告, 才恍然大悟判断唯一得用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[][], vis[][][], ans[][], v[], d[][], pre[], relation[];
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]) % ;//类似于种类并查集的更新
}
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) % ;
}
} void dp()
{
int k = ;
for(int i = mi+; i <= (n1+n2); i++)
{
if(v[i] == )
{
k++;
int t1 = ans[i][];
int t2 = ans[i][];
int mx = min(t1, t2);
for(int j = n1; j >= mx; j--)
{
d[k][j] = d[k-][j-t1] + d[k-][j-t2];
if(d[k-][j-t1] == && d[k-][j-t2] == )
{
vis[k][j][] = i;
vis[k][j][] = ;
}
else if(d[k-][j-t2] == && d[k-][j-t1] == )
{
vis[k][j][] = i;
vis[k][j][] = ;
}
}
}
}
}
int main()
{
while(scanf("%d%d%d", &n, &n1, &n2) != EOF)
{
if(n == && n1 == && n2 == )
break;
//初始化所有节点得父节点和relation
for(int i = ; i <= n1+n2; i++){pre[i] = i; relation[i] = ;}
for(int i = ; i <= n; i++)
{
int a, b;
char c[];
scanf("%d%d%s", &a, &b, &c);
if(strcmp(c, "yes") == )
work(a, b, );
else if(strcmp(c, "no") == )
work(a, b, );
}
//这里注意一下:到这一步,有可能存在一些点的父节点不是最跟的节点
for(int i = ; i <= n1+n2; i++)
int t = find(i);
memset(v, , sizeof(v));
//ans[i][0]表示与最根节点i同类的节点个数, ans[i][1]代表与最根节点i不同类的节点个数
memset(ans, , sizeof(ans));
flag = ;//存储一共有多少个不同的最跟部的父节点
mi = 10e9;
for(int i = ; i <= n1+n2; i++)
{
int x = pre[i];
int y = relation[i];
if(x < mi)
mi = x;
ans[x][y]++;
if(v[x] == )
{
v[x] = ;
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, , sizeof(d));
memset(vis, , sizeof(vis));
d[][ans[mi][]]++; d[][ans[mi][]]++;
vis[][ans[mi][]][] = mi;
vis[][ans[mi][]][] = ;
vis[][ans[mi][]][] = mi;
vis[][ans[mi][]][] = ;
dp();
if(d[flag][n1] == )//如果前flag个集合中累计人数为n1的可能为1时,有唯一解
{
int j = n1;
for(int i = flag; i >= ; i--)//从后往前推
{
a[i][] = vis[i][j][];
a[i][] = vis[i][j][];//记录第i个集合中取得是哪一类(同类0, 不同类1)
j -= ans[a[i][]][a[i][]];
}
for(int i = ; i <= n1+n2; i++)
{
for(int j = ; j <= flag; j++)
{
int f = pre[i];
int ff = relation[i];
if(f == a[j][] && ff == a[j][])
printf("%d\n", i);
}
}
printf("end\n");
}
else
printf("no\n");
}
return ;
}
上一篇:poj 1417 True Liars(并查集+背包dp)


下一篇:poj 1182 食物链(种类并查集 ‘初心者’)