| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我的代码~~!!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator