不斷松弛，直到符合條件或不能松弛。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/5 10:15:15
* File Name: poj1860.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(107);
struct Edge
{
int u,v;
double rate,comm;
};
int n,m,s;
double v;
Edge e[kMaxn*kMaxn*2];int cnt;
void AddEdge(int u,int v,double rate,double comm)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].rate=rate;
e[cnt].comm=comm;
}
bool BellmanFord()
{
double dist[kMaxn];
for(int i=1;i<=n;i++)
dist[i]=(i==s?v:0.0);
while(dist[s]-v<=kEps)
{
bool found(false);
for(int j=1;j<=cnt;j++)
if(dist[e[j].v]-(dist[e[j].u]-e[j].comm)*e[j].rate<-kEps)
{
dist[e[j].v]=(dist[e[j].u]-e[j].comm)*e[j].rate;
found=true;
}
if(!found)
return dist[s]-v>kEps;
}
return (dist[s]-v)>kEps;
}
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d%d%d%lf",&n,&m,&s,&v)==4)
{
cnt=0;
while(m--)
{
int a,b;
double t1,t2,t3,t4;
scanf("%d%d%lf%lf%lf%lf",&a,&b,&t1,&t2,&t3,&t4);
AddEdge(a,b,t1,t2);
AddEdge(b,a,t3,t4);
}
if(BellmanFord())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
posted on 2011-08-05 12:00
lee1r 閱讀(285)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
題目分類(lèi)：圖論