POJ-1417[True Liars]とセット+リュックサック

タイトルの大意:
全部でp 1+p 2人で、2つのグループに分けて、1つのグループp 1、1つのグループp 2です.以下のように、N個の条件が与えられる.
x y yesはxとyが同じグループに分かれていることを表す
x y noはxとyが異なるグループに分かれていることを表す
パケット状況が一意かどうかを尋ね、一意であればシナリオを出力し、そうでなければnoを出力する.矛盾条件がないことを保証しますが、x=yの場合があります.
 
参考資料:http://hi.baidu.com/buaa_babt/blog/item/ff6c6c40ba89a2136a63e53a.html
 
 
CODE:

/*   +  */
/*          DP             ，                     */
/*AC  ：63ms*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <cstring>
#define MAXN 605
using namespace std;
int M,P1,P2,N,scc;
int p[MAXN];//         
int rel[MAXN];//          0:  (yes);1:  (no)
int num[MAXN][2];//num[i][j]       i j    
int root[MAXN];
int dp[MAXN][MAXN];//dp[i][j]        i ,    j      
int pre[MAXN][MAXN];//    
bool ans[MAXN];
int find_set(int x)
{
	if(p[x]!=x)
	{
		int t=find_set(p[x]);
		rel[x]^=rel[p[x]];
		p[x]=t;
	}
	return p[x];
}
void Init()
{
	int i,j,u,v,w;
	char s[10];
	N=P1+P2;
	memset(num,0,sizeof(num));
	//   
	for(i=1;i<=N;i++)
	{
		p[i]=i;
		rel[i]=0;
	}
	for(i=1;i<=M;i++)
	{  
		scanf("%d%d%s",&u,&v,s);
		w=(s[0]=='n');
		int du=find_set(u);
		int dv=find_set(v);
		if(du!=dv)
		{
			p[du]=dv;//                    
			rel[du]=rel[u]^rel[v]^w;
		}
	}
	//   
	for(i=1;i<=N;i++)
		p[i]=find_set(i);
	scc=0;
	for(i=1;i<=N;i++)
	{
		if(p[i]==i)
		{
			scc++;
			root[scc]=i;
			for(j=1;j<=N;j++)
			{if(p[j]==i) ++num[scc][rel[j]];}
		}
	}
}
void Solve()
{
	int i,j,k,x,y;
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(i=1;i<=scc;i++)
	{
		for(j=P1;j>=0;j--)
		for(k=P2;k>=0;k--)
		{
			x=j-num[i][0];y=k-num[i][1];
			if(x>=0&&y>=0&&dp[x][y])
				dp[j][k]+=dp[x][y];
			x=j-num[i][1];y=k-num[i][0];
			if(x>=0&&y>=0&&dp[x][y])
				dp[j][k]+=dp[x][y];
		}
	}
	if(dp[P1][P2]!=1) printf("no
");
	else
	{
		memset(pre,0,sizeof(pre));
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(i=1;i<=scc;i++)
		{
			for(j=P1;j>=0;j--)
			for(k=P2;k>=0;k--)
			{
				if(dp[j][k]) continue;
				x=j-num[i][0];y=k-num[i][1];
				if(x>=0&&y>=0&&dp[x][y])
				{
					dp[j][k]+=dp[x][y];
					pre[j][k]=0;
					continue;
				}
				x=j-num[i][1];y=k-num[i][0];
				if(x>=0&&y>=0&&dp[x][y])
				{
					dp[j][k]+=dp[x][y];
					pre[j][k]=1;
					continue;
				}
			}
		}
		x=P1;y=P2;
		memset(ans,false,sizeof(ans));
		for(i=scc;i>=1;i--)
		{
			for(j=1;j<=N;j++)
			{if(root[i]==p[j]&&rel[j]==pre[x][y]) ans[j]=true;}
			if(pre[x][y])
			{x-=num[i][1];y-=num[i][0];}
			else
			{x-=num[i][0];y-=num[i][1];}
		}
		for(i=1;i<=N;i++)
		{
			if(ans[i])
				printf("%d
",i); 
		}
		printf("end
");
	}
} 
int main()
{
	while(scanf("%d%d%d",&M,&P1,&P2)!=EOF)
	{
		if(M==0&&P1==0&&P2==0) break;
		Init();
		Solve();
	}
	return 0;
}