UVa 11090 Going in Cycle!!【Bellman_Ford】

题意:给出n个点m条边的加权有向图,求平均值最小的回路

自己想的是用DFS找环(真是too young),在比较找到各个环的平均权值,可是代码实现不了,觉得又不太对

后来看书= =好巧妙的办法, 使用二分法求解,首先记录下来这m条边的最大权值ub

然后可以猜测一个mid,只需要判断是否存在平均值小于mid的回路 假设存在一个包含k条边的回路,回路上各条边的权值分别为w1,w,2,w3,----,wk

那么

w1+w2+w3+----+wk<k*mid

又因为联想到Bellman_Ford可以解决负环,把上式转化一下

(w1-mid)+(w2-mid)+(w3-mid)+----(wk-mid)<0

这样先将每条边w(a,b)转化成为w(a,b)-mid,再判断“新”的图中是否存在负环

自己看的时候有两个不明白的,就是最开始判断的时候为什么要用ub+1,

是因为ub+1是最差的答案了,它能够尽可能的使得每条边负得最多,如果在这种情况下都找不到负环,那么一定不存在负环

然后就是如果在ub+1的条件下能够找到负环,那么就二分查找一步步找出平均值最小的环,直到到达循环退出的精度

代码学习的标程= =

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#define mod=1e9+7; using namespace std; typedef long long LL;
const int INF = 0x7fffffff;
const int maxn=; struct Edge{
int from,to; double dist;
}; struct BellmanFord{
int n,m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
double d[maxn];
int p[maxn];
int cnt[maxn]; void init(int n){
this->n=n;
for(int i=;i<n;i++) G[i].clear();
edges.clear();
} void AddEdges(int from,int to,double dist){
edges.push_back((Edge){from,to,dist});
m=edges.size();
G[from].push_back(m-);
} bool negativeCycle(){
queue<int> Q;
memset(inq,,sizeof(inq));
memset(cnt,,sizeof(cnt));
for(int i=;i<n;i++) {d[i]=;inq[]=true;Q.push(i);} while(!Q.empty()){
int u=Q.front();Q.pop();
inq[u]=false;
for(int i=;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(d[e.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;
p[e.to]=G[u][i];
if(!inq[e.to]){
Q.push(e.to);
inq[e.to]=true;
if(++cnt[e.to]>n)
return true;
}
}
}
}
return false;
}
}; BellmanFord solver; bool test(double x){
for(int i=;i<solver.m;i++)
solver.edges[i].dist-=x; bool ret=solver.negativeCycle();
for(int i=;i<solver.m;i++)
solver.edges[i].dist+=x;
return ret;
} int main(){
int T;
scanf("%d",&T);
for(int kase=;kase<=T;kase++){
int n,m;
scanf("%d %d",&n,&m);
solver.init(n);
int ub=;
while(m--){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);u--;v--;ub=max(ub,w);
solver.AddEdges(u,v,w);
}
printf("Case #%d: ",kase);
if(!test(ub+)) printf("No cycle found.\n");
else{
double L=,R=ub;
while(R-L>1e-){
double M=L+(R-L)/;
if(test(M)) R=M;else L=M;
}
printf("%.2lf\n",L);
}
}
return ;
}
上一篇:Java中常用的运算符


下一篇:*[codility]CartesianSequence