POJ 1417 True Liars(并查集+DP) - c++编程基础

题目：给出p1+p2个人，其中p1个是好人，p2个是坏人。然后有一些关系，a说b是好人(坏人).其中没有矛盾的，判断是否有唯一解判断哪些人是好人，哪些人是坏人。

其中比较重要的是，好人总说真话，坏人总说假话。不需要判断矛盾。

其中好人说真话，坏人说假话这点很重要。

那么如果一个人说另一个人是好人，那么如果这个人是好人，说明对方确实是好人，如果这个是坏人，说明这句话是假的，对方也是坏人。

如果一个人说另一个人是坏人，那么如果这个人是好人，说明对方是坏人，如果这个是坏人，说明对方是好人。

也就是如果条件是yes说明这两个是相同集合的，否则是两个不同的集合。

用r[i]表示i结点与根结点的关系，0为相同集合，1为不同集合。这是一个经典的并查集问题。

这样处理之后，还需要判断是否唯一

我们通过并查集，可以将所有人分为若干个集合，其中对于每一个集合，又分为两个集合（好人和坏人，但是不知道哪些是好人，哪些是坏人，我们只有相对关系）

接下来就是从所有大集合中的两个小集合取一个，组成好人集合，判断是否唯一。

背包问题，dp[i][j]表示前i个大集合，好人为j个的方案有多少种，或者dp[i][j]表示当前好人i个，坏人j个的情况有多少种

如果dp[cnt][p1]！=1说明方案不唯一，或者无解。

如果为1题目还需要输出方案，这点比较纠结。用后一种DP的时候WA了好多次，而这题又卡内存，不能开三维数组，其实可以两次DP解决。

后来采用前者DP，不断从dp[cnt][p1]往前递推，递推的结果也必须是某个前趋状态的dp值为1.

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 1<<30
#define M 60005
#define N 605
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a) #define Min(a,b) ((a)<(b) (a):(b))
#define Max(a,b) ((a)>(b) (a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
using namespace std;
int pre[N],r[N];
int p1,p2,p;
bool vis[N];
int dp[N][N/2];
int cnt; //最后分为几个集合
int a[N][2]; //a[i][0],a[i][1]分别表示把第i个集合分成的两个部分
vector b[N][2];
int find(int x)
{
if(x!=pre[x])
{
int f=pre[x];
pre[x]=find(pre[x]);
r[x]=r[x]^r[f];
}
return pre[x];
}
void Init()
{
for(int i=1; i<=p1+p2; i++) pre[i]=i,r[i]=0;
mem(vis,false);
cnt=1;
mem(a,0);
for(int i=0; i {
b[i][0].clear();
b[i][1].clear();
}
}
int main()
{
while(scanf("%d%d%d",&p,&p1,&p2)!=EOF&&p+p1+p2)
{
Init();
while(p--)
{
int u,v;
char str[10];
scanf("%d%d%s",&u,&v,str);
int k=(str[0]=='n');
int ra=find(u),rb=find(v);
if(ra!=rb)
{
pre[ra]=rb;
r[ra]=r[u]^r[v]^k;
}
}
for(int i=1; i<=p1+p2; i++)
{
if(!vis[i])
{
int f=find(i);
for(int j=i; j<=p1+p2; j++)
{
if(find(j)==f)
{
vis[j]=true;
b[cnt][r[j]].pb(j);
a[cnt][r[j]]++;
}
}
cnt++;
}
}
mem(dp,0);
dp[0][0]=1;
for(int i=1; i {
for(int j=p1; j>=0; j--)
{
if(j-a[i][0]>=0)
dp[i][j]+=dp[i-1][j-a[i][0]];
if(j-a[i][1]>=0)
dp[i][j]+=dp[i-1][j-a[i][1]];
}
}
if(dp[cnt-1][p1]!=1)
{
printf("no\n");
continue;
}
else
{
vectorans;
ans.clear();
for(int i=cnt-1; i>=1; i--)
{
if(p1-a[i][0]>=0&&p2-a[i][1]>=0&&dp[i-1][p1-a[i][0]]==1)
{
for(int j=0; j {
ans.pb(b[i][0][j]);
}

POJ 1417 True Liars(并查集+DP) (一)