目录
BZOJ1486 最小圈题解ｃｏｄｅ
BZOJ1486 最小圈
题目传送门
题解
二分＋找负环。我们二分最小的平均值，每次check的时候，将原图中的每条边都减去这个平均值，然后在图中找是否有负环，如果找到有负环，则说明存在至少一个环使得这个环的平均值小于当前的值，于是就可以减小右边界，反之增大左边界。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int N=3005;
const int M=5e4+500;
const double eps=1e-9;
const double inf=1e9+7;
int n,m,Cnt,tot;
double Mx,Mn;
bool can;
struct edge {
int to,nxt;
double w;
}E[M];
int head[N],vis[N];
double dis[N];
/*==================Define Area================*/
void addedge(int u,int v,double w) {
E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;E[tot].w=w;
}
int Dfs(int o) {
vis[o]=1;
for(int i=head[o];~i;i=E[i].nxt) {
int to=E[i].to;
if(dis[to]>dis[o]+E[i].w) {
if(vis[to]) {
can=1;
break;
}
else {
dis[to]=dis[o]+E[i].w;
Dfs(to);
}
}
}
vis[o]=0;
}
bool check(double mid) {
for(int i=1;i<=tot;i++) E[i].w-=mid;
memset(vis,0,sizeof vis);
memset(dis,0,sizeof dis);
can=0;
for(int i=1;i<=n;i++) {
Dfs(i);
if(can) {
for(int i=1;i<=tot;i++) E[i].w+=mid;
return 1;
}
}
for(int i=1;i<=tot;i++) E[i].w+=mid;
return 0;
}
int main() {
memset(head,-1,sizeof head);
read(n);read(m);
Mx=-inf;
Mn=inf;
double w;
for(int i=1,u,v;i<=m;i++) {
read(u);read(v);
scanf("%lf",&w);
addedge(u,v,w);
Mx=max(Mx,w);
Mn=min(Mn,w);
}
Cnt=60;
double L=Mn,R=Mx,ans;
while(Cnt--) {
double Mid=(L+R)/2.0;
if(!check(Mid)) {
L=Mid+eps;
ans=Mid;
}
else R=Mid-eps;
}
printf("%.8lf\n",ans);
return 0;
}
/*
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
*/
转载于:https://www.cnblogs.com/Apocrypha/p/9434933.html
