| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
答案wa,但是评论区的数据都过了,拿AC代码写对拍也没查出来问题#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int M=601,N=2001;
int n,p1,p2,m;
int f[M*2],s[M*2],dp[M][N],from[M][N],ts[M],ans[M*2];
int find(int x)
{
if(x==f[x])
{
return f[x];
}
f[x]=find(f[x]);
return f[x];
}
void bind(int x,int y)
{
if(x==y)
{
return;
}
if(s[x]>s[y])
{
f[y]=x;
s[x]+=s[y];
}
else
{
f[x]=y;
s[y]+=s[x];
}
return;
}
int main()
{
while(scanf("%d%d%d",&n,&p1,&p2))
{
int tot=0;
if(!n && !p1 && !p2)
{
break;
}
m=p1+p2;
for(int i=1;i<=m*2;i++)
{
f[i]=i;
s[i]=1;
}
memset(dp,0,sizeof(dp));
memset(ans,0,sizeof(ans));
memset(ts,0,sizeof(ts));
for(int i=1;i<=n;i++)
{
int a,b;
char s[10];
scanf(" %d%d %s",&a,&b,s);
int a1=find(a),a2=find(a+m);
int b1=find(b),b2=find(b+m);
if(s[0]=='y')
{
bind(a1,b1);
bind(a2,b2);
}
else
{
bind(a1,b2);
bind(a2,b1);
}
}
//判断过程
if(p1==p2)
{
printf("no\n");
continue;
}
dp[0][0]=1;
for(int i=1;i<=m;i++)
{
int k=find(i);
if(k>m)
{
continue;
}
ts[k]++;
}
for(int i=1;i<=m;i++)
{
if(f[i]!=i)
{
continue;
}
tot++;
for(int j=0;j<=p1;j++)
{
if(dp[tot-1][j])
{
if(j+ts[i]<=p1)
{
dp[tot][j+ts[i]]+=dp[tot-1][j];
from[tot][j+ts[i]]=i;
}
if(j+s[i]-ts[i]<=p1)
{
dp[tot][j+s[i]-ts[i]]+=dp[tot-1][j];
from[tot][j+s[i]-ts[i]]=m+i;
}
}
}
}
if(!dp[tot][p1] || dp[tot][p1]>1)
{
printf("no\n");
}
else
{
int r=p1;
while(r)
{
ans[from[tot][r]]=1;
if(from[tot][r]<=m)
{
r-=ts[from[tot][r]];
}
else
{
r-=s[from[tot][r]-m]-ts[from[tot][r]-m];
}
tot--;
}
for(int i=1;i<=m;i++)
{
if(ans[f[i]])
{
printf("%d\n",i);
}
}
printf("end\n");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator