程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1417 True Liars

poj 1417 True Liars

編輯:C++入門知識

題目大意:
某一島上有p1個只說真話的人(好人),p2個只說謊話的人(壞人),所有人都有一個唯一的編號(1~p1+p2)詢問n次.
詢問格式 a b res:
問a號,b號是否是好人,res可以是yes或者no.
判斷是否能找出所有好人,可以的話輸出好人的編號再加個end,否則輸出no.

題目思路:
當回答是yes:
如果a是好人,那麼b肯定也是好人,反之a是壞人,那麼b也肯定是壞人.
所以回答是yes時,a和b是同一類人. www.2cto.com
當回答是no時,同樣可以證明,a和b不是同一類人.
所以我們可以用並查集把所有可以判斷是否同類的人歸在一個集合.
之後我們就要判斷是否有唯一的一種組合使得有p1個人為好人.
這裡我們可以用到dp,因為這個很像背包.
dp[i][j],表示前i個集合中有j人是好人的組合有幾個.
顯然如果dp[集合數][p1]如果等於1,那麼就是有答案了.
狀態方程也很容易推導的.

代碼:
[cpp] 
#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 
#include <ctype.h> 
#include <math.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
#define ll long long 
#define ls rt<<1 
#define rs ls|1 
#define lson l,mid,ls 
#define rson mid+1,r,rs 
#define middle (l+r)>>1 
#define eps (1e-8) 
#define type int 
#define clr_all(x,c) memset(x,c,sizeof(x)) 
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1)) 
#define MOD 1000000009 
#define INF 0x3f3f3f3f 
#define pi acos(-1.0) 
#define _max(x,y) (((x)>(y))? (x):(y)) 
#define _min(x,y) (((x)<(y))? (x):(y)) 
#define _abs(x) ((x)<0? (-(x)):(x)) 
#define getmin(x,y) (x= (x<0 || (y)<x)? (y):x) 
#define getmax(x,y) (x= ((y)>x)? (y):x) 
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;} 
int TS,cas=1; 
const int M=1200+5; 
int n,p1,p2; 
int fa[M],vis[M],tot,dp[M][M]; 
vector<int>a[M][2]; 
int res[M],m,pre; 
 
int find(int x){ 
    return (fa[x]==x)? x:(fa[x]=find(fa[x])); 

 
void uni(int x,int y){ 
    fa[find(x)]=find(y); 

 
void run(){ 
    int i,j; 
    for(i=1;i<=2*(p1+p2);i++) fa[i]=i; 
    char op[11]; 
    while(n--){ 
        scanf("%d%d%s",&i,&j,op); 
        if(op[0]=='y') uni(i,j),uni(i+p1+p2,j+p1+p2); 
        else uni(i,j+p1+p2),uni(i+p1+p2,j); 
    } 
    bool ok=1; 
    clr_all(vis,0); 
    for(i=1;i<=p1+p2;i++){ 
        if(find(i) == find(i+p1+p2)){ 
            puts("no"); 
            return; 
        } 
    } 
    tot=0; 
    for(i=1;i<=p1+p2;i++) if(!vis[i]){ 
        int f0=find(i),f1=find(i+p1+p2); 
        ++tot; 
        a[tot][0].clear(); 
        a[tot][1].clear(); 
        for(j=1;j<=p1+p2;j++) if(!vis[j]){ 
            int jf=find(j); 
            if(jf==f0) a[tot][0].push_back(j),vis[j]=1; 
            else if(jf==f1) a[tot][1].push_back(j),vis[j]=1; 
        } 
    } 
    for(i=1;i<=tot;i++){ 
         
    } 
    clr_all(dp,0); 
    dp[0][0]=1; 
    for(i=1;i<=tot;i++){ 
        int sz0=a[i][0].size(); 
        int sz1=a[i][1].size(); 
        for(j=p1;j>=sz0;j--) dp[i][j]+=dp[i-1][j-sz0]; 
        for(j=p1;j>=sz1;j--) dp[i][j]+=dp[i-1][j-sz1]; 
    } 
    if(dp[tot][p1]==1){ 
        m=0; 
        pre=p1; 
        for(i=tot;i>=1;i--){ 
            int sz0=a[i][0].size(); 
            if(dp[i-1][pre-sz0]==1){ 
                pre-=sz0; 
                for(j=0;j<sz0;j++) res[++m]=a[i][0][j]; 
                continue; 
            } 
            int sz1=a[i][1].size(); 
            if(dp[i-1][pre-sz1]==1){ 
                pre-=sz1; 
                for(j=0;j<sz1;j++) res[++m]=a[i][1][j]; 
                continue; 
            } 
             
        } 
        sort(res+1,res+m+1); 
        for(i=1;i<=m;i++) printf("%d\n",res[i]); 
        puts("end"); 
    }else puts("no"); 

 
void preSof(){ 

 
int main(){ 
    //freopen("input.txt","r",stdin); 
    //freopen("output.txt","w",stdout); 
    preSof(); 
    //run(); 
    while(~scanf("%d%d%d",&n,&p1,&p2) && (n||p1||p2)) run(); 
    //for(scanf("%d",&TS);cas<=TS;cas++) run(); 
    return 0; 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved