POJ1417 True Liars 并查集动态规划（种类并查集）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - POJ1417

题意概括

有一群人，p1个好人，p2个坏人。

他们说了n句话。(p1+p2<=600,n<=1000)

说话的格式是这样的：

x y yes或者x y no

分别表示x说y是/不是好人。

其中好人说真话，坏人说假话。

现在给出这些话。

如果自相矛盾或者有多种满足条件的情况，那么输出no。

否则从小到大输出好人的编号，输出完之后输出一个end（占一行）。

有多组数据。

注意n==0的情况

题解

这题还是比较复杂的。

首先跑一跑种类并查集。

我们发现，一个人如果说了yes，那么x与y是一帮的，否则不是一帮的。

于是，我们可以根据这个建立种类并查集，表示他们的敌对关系。

然后我们首先可以把自相矛盾的情况判掉。

（如果p1==p2，一定是no）

然后我们把所有的关系处理出来，格式为：

v,x,y，x,y分别为两个敌对集团的人数(y可以为0)，而v表示x集团的祖先。

假设总共弄出了cnt个敌对集团组。

这个预处理方便了之后的操作。

然后用dp[i][j]表示在前i个集团里面选择j个好人的方案数。

我们可以用类似背包的做法求出整个dp数组。

最后dp[cnt][p1]如果不等于1，那么要么多解，要么无解，所以输出no

dp的过程中有可能会溢出，但是我们的dp只需要知道3种性质就可以了，分别是0,1,>1三种。

想想为什么……

所以当dp[i][j]比较大的时候，我们可以人为的把它弄小。

不输出no的情况，我们从dp倒着回推，就可以找出方案。

详细操作见代码。

代码

#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=1005;
int n,m,p1,p2,fa[N*2],dp[N][N],cnt=0,f[N],ans[N],tot;
//dp[i][j]表示在前i个集合中选择j个好人的方案总数
struct Set{
int v,x,y;
Set (){}
Set (int a,int b,int c){
v=a,x=b,y=c;
}
}s[N];
int getf(int k){
return fa[k]==k?k:fa[k]=getf(fa[k]);
}
void plus(int &a,int b){
a=min(10,a+b);
}
void getans(int cnt,int rem){
if (cnt==0)
return;
int nc=cnt-1,rx=rem-s[cnt].x,ry=rem-s[cnt].y;
if (rx>=0&&dp[nc][rx]==1){
getans(nc,rx);
for (int i=1;i<=n;i++)
if (getf(i)==s[cnt].v)
ans[++tot]=i;
}
else if (ry>=0&&dp[nc][ry]==1){
getans(nc,ry);
for (int i=1;i<=n;i++)
if (getf(i+n)==s[cnt].v)
ans[++tot]=i;
}
}
int main(){
while (~scanf("%d%d%d",&m,&p1,&p2)&&(m||p1||p2)){
n=p1+p2;
for (int i=1;i<=n*2;i++)
fa[i]=i;
bool flag=1;
for (int i=1;i<=m;i++){
char s[5];
int a,b;
scanf("%d%d%s",&a,&b,s);
if (a==b&&s[0]=='n')
flag=0;
if (s[0]=='y'){
if (getf(a)==getf(b+n))
flag=0;
fa[getf(a)]=getf(b);
fa[getf(a+n)]=getf(b+n);
}
else {
if (getf(a)==getf(b))
flag=0;
fa[getf(a)]=getf(b+n);
fa[getf(b)]=getf(a+n);
}
}
if (!flag||p1==p2){
puts("no");
continue;
}
cnt=0;
memset(f,0,sizeof f);
for (int i=1;i<=n;i++){
if (f[i])
continue;
s[++cnt]=Set(getf(i),0,0);
for (int j=i;j<=n;j++){
if (f[j])
continue;
if (getf(j)==getf(i))
s[cnt].x++,f[j]=1;
else if (getf(j+n)==getf(i))
s[cnt].y++,f[j]=1;
}
}
memset(dp,0,sizeof dp);
dp[0][0]=1;
for (int i=1;i<=cnt;i++)
for (int j=0;j<=n;j++){
if (dp[i-1][j]==0)
continue;
int a=j+s[i].x,b=j+s[i].y;
if (a<=n)
plus(dp[i][a],dp[i-1][j]);
if (b<=n)
plus(dp[i][b],dp[i-1][j]);
}
if (dp[cnt][p1]!=1){
puts("no");
continue;
}
tot=0;
memset(ans,0,sizeof ans);
getans(cnt,p1);
sort(ans+1,ans+tot+1);
for (int i=1;i<=tot;i++)
printf("%d\n",ans[i]);
puts("end");
}
return 0;
}