本文主要是介绍poj-3621-Sightseeing Cows-01分数规划+spfa判负环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
假如最终的答案是re。
那么对每条边进行一定的处理。
然后用spfa判断是否出现了负环。
如果出现了负环。说明所取的re偏小。
就这样二分re。
spfa判断负环的方法是如果某个点入队列超过n次，那么图中存在负环。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define maxn 220000
#define maxeg 5500
#define maxpt 1100
#define INF 99999999
#define eps 1e-3
#define zero(x) ((fabs(x)<eps)?0:x)
struct G
{int num;int head[maxpt];struct list{int u,v,next;double w;}edge[maxeg*2+1000];void init(){memset(head,-1,sizeof(head));num=0;}void add(int u,int v,double w){edge[num].u=u;edge[num].v=v;edge[num].w=w;edge[num].next=head[u];head[u]=num++;}
}gra;
double val[maxpt];
double dist[maxpt];
int times[maxpt];
int vis[maxpt];
int n,m;
int spfa(double re)
{int i;for(i=1;i<=n;i++){dist[i]=INF;times[i]=0;vis[i]=0;}queue<int>que;while(!que.empty())que.pop();times[1]++;vis[1]=1;que.push(1);dist[1]=0;while(!que.empty()){int u=que.front();que.pop();vis[u]=0;for(i=gra.head[u];i!=-1;i=gra.edge[i].next){int v=gra.edge[i].v;double w=gra.edge[i].w;double ad=-(val[u]-1.0*re*w);if(dist[u]+ad<dist[v]){dist[v]=dist[u]+ad;if(!vis[v]){que.push(v);times[v]++;vis[v]=1;if(times[v]>=n)return 1;}}}}return 0;
}
int main()
{int i,a,b;double c;scanf("%d%d",&n,&m);gra.init();for(i=1;i<=n;i++)scanf("%lf",&val[i]);for(i=1;i<=m;i++){scanf("%d%d%lf",&a,&b,&c);gra.add(a,b,c);}double l=0.0;double r=1000.0;double mid=(l+r)/2;while(zero(r-l)>0){mid=(l+r)/2;if(spfa(mid))l=mid;else r=mid;// cout<<l<<" "<<r<<" "<<mid<<endl;}printf("%.2f\n",mid);return 0;
}这篇关于poj-3621-Sightseeing Cows-01分数规划+spfa判负环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
