poj 1417 True Liars （并查集+dp） - c++编程基础

nd 3 4 5 6 end

Source

Japan 2002 Kanazawa

题意：

给出p1+p2个人，其中p1个是好人，p2个是坏人。好人只说真话，坏人只说假话，有一些关系，a说b是好人(坏人).其中没有矛盾的，判断是否有唯一解判断哪些人是好人，哪些人是坏人。

思路来源于：cxlove博客

思路：

a说b是好人，那么a、b是同种人的，a说b是坏人，那么a、b不是同种人，用并查集维护每个有关系的集合，集合存和root关系相同的有多少人、不同的有多少人，然后dp。

dp[i][j] 前i个集合有j个好人的种数。

用一个数组纪录路径，不过要输出方案貌似还要一点处理，我是通过建图处理的，代码写的好长，衰~

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 1005 #define MAXN 2005 #define mod 1000000009 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; int n,m,ans,cnt,tot,flag; int p1,p2; int num[maxn][2],pre[maxn],dp[maxn][maxn],vis[maxn],pp[maxn]; int path[maxn][maxn],mp[maxn],ok[maxn][maxn],tmp[maxn],vv[maxn]; int X[maxn],Y[maxn]; char s[maxn][10]; struct Node { int v,w,next; } edge[10005]; vector
             
              res; void addedge(int u,int v,int w) { tot++; edge[tot].v=v; edge[tot].w=w; edge[tot].next=pp[u]; pp[u]=tot; } int Find(int x) { if(x==pre[x]) return x; pre[x]=Find(pre[x]); return pre[x]; } void Merge(int x,int y) { int u=Find(x),v=Find(y); if(u!=v) { if(ok[u][v]) { pre[u]=v; num[v][1]+=num[u][1]; num[v][0]+=num[u][0]; } else { pre[u]=v; num[v][1]+=num[u][0]; num[v][0]+=num[u][1]; } } } void dfs(int u,int k,int r) // k-是否与根相同 r-要找的点 { if(k==r) res.push_back(u); int i,j,t,v; for(i=pp[u]; i; i=edge[i].next) { v=edge[i].v; if(!vis[v]) { vis[v]=1; dfs(v,k^(!edge[i].w),r); } } } void dfs1(int u,int k) { tmp[u]=k; int i,j,t,v; for(i=pp[u];i;i=edge[i].next) { v=edge[i].v; if(!vis[v]) { vis[v]=vv[v]=1; dfs1(v,k^(!edge[i].w)); } } } void presolve() // 预处理ok[i][j] i和j的属性是否相同 { int i,j,t; memset(vis,0,sizeof(vis)); for(i=1; i<=p1+p2; i++) { if(!vis[i]) { memset(tmp,0,sizeof(tmp)); memset(vv,0,sizeof(vv)); vis[i]=vv[i]=1; dfs1(i,1); vector
              
               tt,tx; for(j=1;j<=p1+p2;j++) { if(vv[j]) tt.push_back(j),tx.push_back(tmp[j]); } for(j=0;j
               
                =num[x][0]) { dp[cnt][j]+=dp[cnt-1][j-num[x][0]]; if(dp[cnt][j]) { path[cnt][j]=j-num[x][0]; } } if(j>=num[x][1]) { int last=dp[cnt][j]; dp[cnt][j]+=dp[cnt-1][j-num[x][1]]; if(dp[cnt][j]!=last) { path[cnt][j]=j-num[x][1]; } } } } } res.clear(); if(dp[cnt][p1]==1) { int now=p1; for(i=cnt; i>=1; i--) { int cxx=path[i][now],k; if(now-cxx==num[mp[i]][1]) k=1; else k=0; if(now==cxx) continue ; memset(vis,0,sizeof(vis)); vis[mp[i]]=1; dfs(mp[i],1,k); now=cxx; } sort(res.begin(),res.end()); for(i=0; i

poj 1417 True Liars （并查集+dp）(二)