【POJ3621】【洛谷2868】Sightseeing Cows（分数规划）

题面

Vjudge

洛谷

大意：

在有向图图中选出一个环，使得这个环的点权\(/\)边权最大

题解

分数规划

二分答案之后把每条边的边权换为\(mid·\)边权-出点的点权

然后检查有没有负环就行啦

#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 1111

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,m,U[5555],V[5555],W[5555];

int a[MAX];

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

int h[MAX],cnt=1;

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

stack<int> S;

int ins[MAX];

double dis[MAX];

bool vis[MAX];

bool SPFA()

{

	while(!S.empty())S.pop();

	for(int i=1;i<=n;++i)vis[i]=true,ins[i]=1,S.push(i),dis[i]=0;

	while(!S.empty())

	{

		int u=S.top();S.pop();

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

		{

			int v=e[i].v;

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

			{

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

				if(!vis[v])S.push(v),vis[v]=true,++ins[v];

				if(ins[v]>=n)return true;

			}

		}

		vis[u]=false;

	}

	return false;

}

bool check(double mid)

{

	for(int i=1;i<=n;++i)h[i]=0;cnt=1;

	for(int i=1;i<=m;++i)Add(U[i],V[i],1.0*W[i]*mid-a[V[i]]);

	if(SPFA())return true;

	return false;

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;++i)a[i]=read();

	for(int i=1;i<=m;++i)U[i]=read(),V[i]=read(),W[i]=read();

	double l=0,r=1e6;

	while(r-l>1e-3)

	{

		double mid=(l+r)/2;

		if(check(mid))l=mid;

		else r=mid;

	}

	printf("%.2f\n",l);

	return 0;

}