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

直接用spfa过嘛,判回路,超过|v|返回

Posted by TSERROF at 2012-12-04 21:50:38 on Problem 1860
#include<iostream>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 102
#define  INF 0xffff
int N,M,S;
double V;
float ratio[MAXN][MAXN];
float commisions[MAXN][MAXN];
float map[MAXN][MAXN];
bool spfa()
{
	bool inqueue[MAXN];
	int h[MAXN];
	float l[MAXN];
	fill(inqueue,inqueue+N+1,false);
	fill(l,l+N+1,0);
	fill(h,h+N+1,0);
	queue<int>q;
	q.push(S);
	l[S]=V;
	bool flag=false;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		inqueue[x]=false;
		++h[x];
		if(h[x]>N) { flag=true;break;}
		for(int i=1;i<=N;++i)
		{
			if(map[x][i]!=INF && l[i]<(l[x]-commisions[x][i])*ratio[x][i] )
			{
				l[i]=(l[x]-commisions[x][i])*ratio[x][i] ;
				if(!inqueue[i])
				{
					inqueue[i]=true;
					q.push(i);
				}
			}
		}
	}
	return flag;
};
int main()
{
	while(cin>>N>>M>>S>>V)
	{
		for(int i=1;i<=N;++i)
			for(int j=1;j<=N;++j)
				map[i][j]=INF;
		for(int i=1;i<=M;++i)
		{
			int A,B;
			cin>>A>>B;
			cin>>ratio[A][B]>>commisions[A][B]>>ratio[B][A]>>commisions[B][A];
			map[A][B]=map[B][A]=0;
		}
		if(spfa())cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	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