| ||||||||||
| 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