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

我的代码~~!!

Posted by stars at 2005-03-22 22:55:14 on Problem 1860
In Reply To:我用bellman-ford做了,但是总是WA,考虑了v=0的情况。faint中…… Posted by:stars at 2005-03-22 22:51:15
#include<iostream>
using namespace std;

const int maxn=100;

int n,m,s;
double v,d[maxn];

double exc[maxn][maxn];

struct Edge {
	int u,
		v;
}edge[maxn];

void iss() {	//initialize_single_source
	for(int i=0;i<n;i++) {
		d[i]=0;
	}
	d[s]=1;
}

void relax(int u,int v) {
	if(d[v]<d[u]*exc[u][v]) {
		d[v]=d[u]*exc[u][v];
	}
}

bool bf() {	//bellman_ford
	int i,j;
	iss();

	for(i=0;i<n-1;i++) {
		for(j=0;j<m;j++) {
			relax(edge[j].u,edge[j].v);
			relax(edge[j].v,edge[j].u);
		}
	}

	for(i=0;i<m;i++) {
		int u=edge[i].u, v=edge[i].v;
		if(d[v]<d[u]*exc[u][v] || d[u]<d[v]*exc[v][u]) return false;
	}

	return true;
}

int main() {
	cin>>n>>m>>s>>v;
	s--;	//start from 0
	for(int i=0;i<m;i++) {
		int a,b;
		double r1,c1,r2,c2;
		cin>>a>>b>>r1>>c1>>r2>>c2;
		a--; b--;
		exc[a][b]=(1-c1/100)*r1;
		exc[b][a]=(1-c2/100)*r2;
		edge[i].u=a;
		edge[i].v=b;
	}
	if(v!=0&&!bf()) cout<<"YES\n";
	else cout<<"NO\n";

	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