POJ 3621 Sightseeing Cows （(二分+spfa求回路 | 最优比率环）
#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;const int VM=1010;const int EM=5010;const int INF=0x3f3f3f3f;struct Edge{ int to,nxt; int cap;}edge[EM<<1];int n,m,cnt,head[VM];int happy[VM],vis[VM],count[VM];double dis[VM];void addedge(int cu,int cv,int cw){ edge[cnt].to=cv; edge[cnt].cap=cw; edge[cnt].nxt=head[cu]; head[cu]=cnt++;}int SPFA(double mid){ queue<int> q; while(!q.empty()) q.pop(); for(int i=1;i<=n;i++){ dis[i]=INF; vis[i]=0; count[i]=0; } dis[1]=0; q.push(1); vis[1]=1; count[1]++; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; double newdis=mid*edge[i].cap-happy[v]; //新的边权值 if(dis[v]>dis[u]+newdis){ dis[v]=dis[u]+newdis; if(!vis[v]){ vis[v]=1; count[v]++; q.push(v); if(count[v]>=n) //有负权环路 return 0; } } } } return 1; //无负权环路}int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ cnt=0; memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++) scanf("%d",&happy[i]); int u,v,w; while(m--){ scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); } double l=0,r=10000,ans=0,mid; while(r-l>=1e-8){ mid=(l+r)/2; if(SPFA(mid)) r=mid; else{ //有负权环路 ans=mid; l=mid; } } printf("%.2f\n",ans); } return 0;}?