Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

上面是用链表写的超时,怎么会这么慢呢??下面是用矩阵写的AC,

Posted by zsc08_wangqiang at 2010-08-24 20:42:50 on Problem 1274
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator