poj 1860 bellman 求正环

#include<stdio.h>
#include<string.h>
#include<queue>//只需判断是否有正环路径就可以了
using namespace std;
#define N  200
struct node {
double r,c;
}map[N][N];
double maxvalue[N],h;
int n,cou[N];
int  bellmanford(int start) {
  queue<int>q;
  int vis[N];
   int cur,i,count=0;
   memset(vis,0,sizeof(vis));
   cou[start]=1;
   vis[start]=1;
   q.push(start);
   while(!q.empty()) {
    cur=q.front();
q.pop();
for(i=1;i<=n;i++) {
if(cur==i)
continue;
if(map[cur][i].c<0||map[cur][i].r<0)
continue;
if(maxvalue[i]<(maxvalue[cur]-map[cur][i].c)*map[cur][i].r&&(maxvalue[cur]-map[cur][i].c)*map[cur][i].r>=0) {
maxvalue[i]=(maxvalue[cur]-map[cur][i].c)*map[cur][i].r;
if(!vis[i]) {
vis[i]=1;
q.push(i);
if(++cou[i]>=n)//如果入队达到n次就说明肯定有正环路径
return 1;
}
}
}
vis[cur]=0;
   }
   return 0;
}
int main() {
int m,i,num,a,b,j;
double ab,abc,ba,bac;
while(scanf("%d%d%d%lf",&n,&m,&num,&h)!=EOF) {
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) {
map[i][j].r=-1;
map[i][j].c=-1;
}
for(i=1;i<=n;i++)
maxvalue[i]=0;
 maxvalue[num]=h;
 for(i=1;i<=m;i++) {
 scanf("%d%d%lf%lf%lf%lf",&a,&b,&ab,&abc,&ba,&bac);
 map[a][b].r=ab;
 map[a][b].c=abc;
 map[b][a].r=ba;
 map[b][a].c=bac;
 }
       if(bellmanford(num))
  printf("YES ");
  else
  printf("NO ");
}
return 0;
}
原文地址:https://www.cnblogs.com/thefirstfeeling/p/4410820.html