我的总是WA
#include<iostream>
using namespace std;
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<string>
#include<map>
#include<set>
#include<queue>
double rate[101][101],c[101][101],r1,r2,c1,c2;
double d[101];
double vs;
#define eps 1e-8
bool relax(int u,int v)
{
	if (d[v]+eps<(d[u]-c[u][v])*rate[u][v]){ 
		d[v]=(d[u]-c[u][v])*rate[u][v];
		return true;
	}
	else return false;
}
bool spfa(int s,int n)
{
	int f=0,r=1,p=1,i,j;
	int q[101],t[101];
	bool in[101];
	memset(in,false,sizeof(in));
	memset(t,0,sizeof(t));
	q[1]=s;
	in[s]=true;
	t[s]++;
	while (f!=r)
	{
		f=f%n+1;
		int front=q[f];
		in[front]=false;
		for (i=1;i<=n;i++)
			if ((!in[i])&&rate[front][i]>eps)
			{
				if (relax(front,i)) {
					in[i]=true,r=r%n+1,q[r]=i,t[i]++;
					if (i==s) return false;
				}
				if (t[i]>n) return false;
			}
	}
	 if (d[s]>vs+eps) return false;
	 else return true;
}
int main(){
	int i,j,n,m,s,a,b;
	memset(d,0,sizeof(d));
	memset(rate,0,sizeof(rate));
	memset(c,0,sizeof(c));
	scanf("%d",&n);
	scanf("%d",&m);
	scanf("%d",&s);
	scanf("%lf",&vs);
	//cout<<v;
	for (i=0;i<m;i++)
	{
		scanf("%d %d",&a,&b);
		scanf("%lf %lf %lf %lf",&r1,&c1,&r2,&c2);
		rate[a][b]=r1;rate[b][a]=r2;c[a][b]=c1;c[b][a]=c2;
	}
	d[s]=vs;
	if (spfa(s,n)) cout<<"NO\n";
	else cout<<"YES\n";
	return 0;
}

• Re:FOXLIU的好方法，让我过了 (3478) hjp_test 2011-07-04 09:02:17