POJ 1417 True Liars(并查集+DP)
题目:给出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<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 60005
#define N 605
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#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<int> 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<N; 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<cnt; 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)
&nbs
补充:软件开发 , C++ ,