Description
找出一个平均边权最小的圈。
Solution
经典问题，二分答案判断有无负环。
但数据范围大，普通spfa会超时，于是用dfs判负环(快多了)。
思路是dis设为0，枚举每个点u，如果d(u)+w<d(v)就搜v，如果搜到的节点曾搜到过说明找到了负环。
为什么是对的呢？对于一个负环，一定可以找到一个节点从这里开始走一直累加权值，权值一直为负。
Code
1 #include<cstdio>
2 #include<algorithm>
3 #include<cstring>
4 using namespace std;
5 const int N=3e5+
5,M=1e4+
5;
6
7 int head[M],e[M],nxt[M],k;
8 double w[M];
9 int adde(
int u,
int v,
double g){
10 e[++k]=v;w[k]=g;nxt[k]=head[u];head[u]=
k;
11 }
12 int n,m;
13
14 double d[N];
15 int vis[N],flag;
16
17 int spfa(
int u){
18 vis[u]=
1;
19 for(
int i=head[u];i;i=
nxt[i]){
20 int v=
e[i];
21 if(d[u]+w[i]<
d[v]){
22 if(vis[v]){flag=
1;
break;}
23 d[v]=d[u]+
w[i];
24 spfa(v);
25 }
26 }
27 vis[u]=
0;
28 }
29
30 int jud(
double mid){
31 for(
int i=
1;i<=k;i++) w[i]-=
mid;
32 memset(d,
0,
sizeof(d));
33 memset(vis,
0,
sizeof(vis));
34 flag=
0;
35 int ret=
0;
36 for(
int i=
1;i<=n;i++
){
37 spfa(i);
38 if(flag){ret=
1;
break;}
39 }
40 for(
int i=
1;i<=k;i++) w[i]+=
mid;
41 return ret;
42 }
43
44 int main(){
45 scanf(
"%d%d",&n,&
m);
46 int u,v;
double g;
47 for(
int i=
1;i<=m;i++
){
48 scanf(
"%d%d%lf",&u,&v,&
g);
49 adde(u,v,g);
50 }
51
52 double l=-1e7,r=
1e7;
53 while(r-l>1e-
10){
54 double mid=(l+r)/
2;
55 if(jud(mid)) r=
mid;
56 else l=
mid;
57 }
58 printf(
"%.8lf",l);
59 return 0;
60 }
转载于:https://www.cnblogs.com/xkui/p/4567878.html
相关资源：数据结构—成绩单生成器
