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 |
上面是用链表写的超时,怎么会这么慢呢??下面是用矩阵写的AC,In Reply To:为啥我都用了cin,cout怎么还是超时啊???? Posted by:zsc08_wangqiang at 2010-08-24 20:02:57 用cin cout 0ms。。用scanf(),printf(),16ms;奇怪啦?? #include<iostream> using namespace std; const int maxn = 201; const int maxm = 201; int uN, vN; bool g[maxn][maxn]; int xM[maxn], yM[maxn]; bool chk[maxn]; bool find(int u) { int v; for(v=1; v<=vN; v++) if(g[u][v] && !chk[v]) { chk[v] = true; if(yM[v] == -1 || find(yM[v])) { yM[v] = u; xM[u] = v; return true; } } return false; } int MaxMatch() { int u, ret = 0; memset(xM, -1, sizeof(xM)); memset(yM, -1, sizeof(yM)); for(u=1; u<=uN; u++) if(xM[u] == -1) { memset(chk, false, sizeof(chk)); if(find(u)) ret++; } return ret; } int main() { int i, j, k, x, y; int ans; while(cin>>uN>>vN) //0ms //while(scanf("%d%d",&uN,&vN) != EOF) //16ms { memset(g, false, sizeof(g)); for(x=1; x<=uN; x++) { cin>>k; //scanf("%d",&k); for(j=1; j<=k; j++) { cin>>y; //scanf("%d",&y); g[x][y] = true; } } ans = MaxMatch(); cout<<ans<<endl; //printf("%d\n",ans); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator