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

想写个BFS版本的,却TLE了,求大神帮忙看看T^T

Posted by lilintong22222 at 2015-05-11 12:18:40 on Problem 3041
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <ctype.h>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <stack>
#include <queue>
#include <sstream>
#include <cmath>
#include <time.h>
#include <map>

using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define repe(i,n) for(int i=1; i<=n; i++)
#define mst(A,k) memset(A,k,sizeof(A))
typedef long long ll;
const int INF = 200000000;
const double inf = 1e13;
const ll MOD = 1000000007;
const double eps = 1e-9;
const int N = 550;
const int M = 10010;

int n,k;
int fst[N],nxt[M],v[M],tol;
int link[N],use[N],pa[N];

void edge(int a,int b)
{
	v[tol] = b;
	nxt[tol] = fst[a];
	fst[a] = tol++;
}
bool Find(int s)
{
	queue<int> Q;
	Q.push(s);
	while(!Q.empty())
	{
		int u = Q.front();Q.pop();
		for(int e=fst[u]; ~e; e=nxt[e])if(!use[v[e]])
		{
			use[v[e]] = 1;
			pa[v[e]] = u;
			if(link[v[e]] != -1)
			{
				Q.push(link[v[e]]);
				pa[link[v[e]]] = v[e];
			}
			else
			{
				int d = v[e];
				link[d] = pa[d];
				d = pa[d];
				while(d != s)
				{
					d = pa[d];
					link[d] = pa[d];
					d = pa[d];
				}
				return true;
			}
		}
	}
	return false;
}
int main()
{
	//freopen("C:\\Users\\Administrator\\Desktop\\out.txt","w",stdout);
	
	int r,c;
	while(~scanf("%d%d",&n,&k))
	{
		tol = 0;
		mst(fst,-1);
		rep(i,k)
		{
			scanf("%d%d",&r,&c);
			edge(r,c);
		}
		mst(link,-1);
		int ans = 0;
		for(int i=1; i<=n; i++)
		{
			mst(use,0);
			if(Find(i)) ans++;
		}
		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