【BZOJ1486】最小圈（分数规划）

题面

BZOJ

洛谷

求图中边权和除以点数最小的环

题解

分数规划

二分答案之后将边权修改为边权减去二分值

检查有无负环即可

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<stack>

using namespace std;

#define ll long long

#define RG register

#define MAX 3003

struct Line{int v,next;double w;}e[10010];

int h[MAX],cnt=1;

inline void Add(int u,int v,double w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

int n,m,U,V;

double dis[MAX],W;

bool vis[MAX];

bool SPFA(int u,double mid)

{

	vis[u]=true;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		if(dis[v]>dis[u]+e[i].w-mid)

		{

			dis[v]=dis[u]+e[i].w-mid;

			if(vis[v]||SPFA(v,mid))return true;

		}

	}

	vis[u]=false;return false;

}

bool check(double mid)

{

	for(int i=1;i<=n;++i)dis[i]=0,vis[i]=false;

	for(int i=1;i<=n;++i)if(SPFA(i,mid))return true;

	return false;

}

int main()

{

	scanf("%d%d",&n,&m);

	double l=+2e7,r=-2e7;

	for(int i=1;i<=m;++i)

	{

		scanf("%d%d%lf",&U,&V,&W);

		l=min(l,W),r=max(r,W),Add(U,V,W);

	}

	while(r-l>1e-9)

	{

		double mid=(l+r)/2;

		if(check(mid))r=mid;

		else l=mid;

	}

	printf("%.8lf\n",l);

	return 0;

}