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