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 |
100*300的数据量我居然去开链表。。不清MLE,清就TLE,后来才反应过来要用邻接矩阵。。AC,顺便加了读入优化 #include<stdio.h> #include<string.h> #include<stdlib.h> #define c(a) memset(a,0,sizeof a) short ans; bool state[310]; short result[310]; short table[110][310]; short n1,n2,m; void initialize(){c(table);ans=0;c(result);} bool hungary(short x) { short i; for(i=1;i<=n2;i++)if(table[x][i]&&!state[i]) { state[i]=1; if(!result[i]||hungary(result[i])) { result[i]=x; return true; } } return false; } inline void scan(short &x) { char c; while(c=getchar(), c<'0'||c>'9'); x=c-'0'; while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0'; } int main() { short T,i,j,y; for(scan(T);T;T--) { initialize(); scan(n1);scan(n2); for(i=1;i<=n1;i++) { scan(m); for(j=1;j<=m;j++)scan(y),table[i][y]=1; } for(i=1;i<=n1;i++) { c(state); if(hungary(i))ans++; } if(ans==n1)printf("YES\n"); else printf("NO\n"); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator