疑似三倍经验

因为和机房一些大佬一起做的这道题，所以emmm他们貌似也写了题解，在做这道题的时候也参照了其他大佬写的一些题解，所以如果程序有雷同请见谅（手动鞠躬）

---

题目也是莫名其妙地给了一大串数学式，简洁地重新说一下题目

给你一张图，图中有环，定义一个环的平均值为环的边权和÷环中点的个数，那么就应该有了一中非常暴力的思路

• 想办法找出来图中所有的环并求出其平均值，再比较出最小值

这个方法确实怎么想都很暴力，但是一点也不好实现，可能是我太弱，我实在想不太出来有什么算法可以找出来所有的环，所以这种思路先给我PASS掉

而正解呢？应该是二分答案。为什么？

• 既然我们找不出来环，我们逆向思维，直接枚举平均值，看是否会有一个环符合条件，那么这道题就变成了：二分枚举平均值，找到是否有环符合条件

若我们此时枚举的平均值为$ans$，有$k$个字符串，那么就有

$ans\ast k=len1+len2+len3+...+lenk$

那道这个式子之后，我们对它进行移项

$0=len1-ans+len2-ans+len3-ans+...+lenk-ans$

那么对于满足以下式子，就可以判断是环了，所以在跑$SPFA$更新距离的时候，就应该像下面这样

$0\le len1-ans+len2-ans+len3-ans+...+lenk-ans$

所以这里就直接给程序了（三道题的）

SP2885 WORDRING - Word Rings

P3199 [HNOI2009]最小圈

#include<bits/stdc++.h>
using namespace std;
const int MAXN=30000000+51;
const double INF=(1e5)*1.0;
const double eqs=1e-9;
int n,m;
struct node {int net,to;double z;
} e[MAXN];
int head[MAXN],tot;
void add(int x,int y,double z) {e[++tot].net=head[x];e[tot].to=y;e[tot].z=z;head[x]=tot;
}double d[MAXN];
bool v[MAXN],flag;
bool spfa(int x,double k) {v[x]=true;for(register int i=head[x]; i; i=e[i].net) {int y=e[i].to;double z=e[i].z;if(d[y]>d[x]+z-k) {d[y]=d[x]+z-k;if(v[y]==true||spfa(y,k)==true) return true;}}v[x]=false;return false;
}
bool check(double x) {for(register int i=1; i<=n; i++) {d[i]=20040915;v[i]=false;}for(register int i=1; i<=n; i++) {if(spfa(i,x)==true) return true;}return false;
}
int main() {scanf("%d%d",&n,&m);for(register int i=1; i<=m; i++) {int x,y;double z;scanf("%d%d%lf",&x,&y,&z);add(x,y,z);}double l=-INF,r=INF;while(r-l>eqs) {double mid=(l+r)/2;if(check(mid)==true) r=mid;else l=mid;}printf("%.8lf",l);return 0;
}

UVA11090 Going in Cycle!!

#include <bits/stdc++.h>
using namespace std;
int T,n,m,u,v,w,tot;
double dis[520010];
int vis[520010],head[520010];struct node {int to,net;double val;
} e[520010];inline void add(int u,int v,double w) {e[++tot].to=v;e[tot].val=w;e[tot].net=head[u];head[u]=tot;
}inline bool dfs(int now,double x) {vis[now]=1;for(register int i=head[now];i;i=e[i].net) {int v=e[i].to;if(dis[v]>dis[now]+e[i].val-x) {dis[v]=dis[now]+e[i].val-x;if(vis[v]==1||dfs(v,x)==true) return true;}}vis[now]=0;return false;
}inline bool check(double x) {for(register int i=1;i<=n;i++) {vis[i]=0;dis[i]=20050206;}for(register int i=1;i<=n;i++) {if(dfs(i,x)==true) return true;}return false;
}int main() {scanf("%d",&T);for(register int k=1;k<=T;k++) {tot=0;for(register int i=1;i<=n;i++) head[i]=0;scanf("%d%d",&n,&m);for(register int i=1;i<=m;i++) {scanf("%d%d%d",&u,&v,&w);add(u,v,w);}double l=-10000000,r=10000000;while(r-l>1e-10) {double mid=(l+r)/2;if(check(mid)==true) r=mid;else l=mid;}printf("Case #%d: ",k);if(l==10000000) puts("No cycle found.");else printf("%.2lf\n",l);}return 0;
}