当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,