01 分数规划

P2868 Sightseeing Cows G

给出一个 \(n\) 个点 \(m\) 条的有点权与边权的有向图，求一个环使得环上的点权和除以边权和最大。

最优比率环问题,显然01分数规划

环上第\(i\)个点点权为\(a_i\),第\(i\)条边的边权为\(b_i\)

#include<cstdio>
#include<queue>
#include<iostream>
#define maxm 5005
#define maxn 1002
using namespace std;
inline int read() {
    int x = 0,f = 1; char s = getchar();
    while(s < ‘0‘ || s > ‘9‘) {if(s == ‘-‘) f = -1;s = getchar();}
    while(s >= ‘0‘ && s <= ‘9‘) {x = x * 10 + s - ‘0‘;s = getchar();}
    return f * x;
}
int l,p,head[maxn],tot = 0,vis[maxn],num[maxn],a[maxn];
double d[maxn];
struct edge{
	int to,next,dis;
}e[maxm];
inline void add(int u,int v,int w){
	e[++tot].to = v;
	e[tot].next = head[u];
	e[tot].dis = w;
	head[u] = tot;
}
int check(double x){//找负环 
	queue<int> q;
	for(int i = 1;i <= l;i++){
		q.push(i);
		d[i] = 0;vis[i] = num[i] = 1;
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();vis[u] = 0;
		for(int i = head[u];i;i = e[i].next){
			int v = e[i].to;
			double dis = (double)e[i].dis;
			if(d[v] > d[u] + x * dis - (double)a[u])//边权为mid*Tim[e_i]-Fun[u_i]
            {
                d[v] = d[u] + x * dis - (double)a[u];
                if(!vis[v])
                {
                    q.push(v); vis[v]=1;
                    if(++num[v] >= l) return 1;
                }
            }
		} 
	}
	return 0;
}
int main(){
 l=read();p=read();
    for(int i=1;i<=l;++i)a[i]=read();
    for(int i=1;i<=p;++i)
    {
        int u=read(),v=read(),dis=read();
        add(u,v,dis);
    }
    double L=0,R=5001,mid;
    while(R-L>1e-4)
    {
        mid=(L+R)/2;
        if(check(mid))L=mid;
        else R=mid;
    }
    printf("%.2lf",L);
    return 0;
}

01 分数规划

原文：https://www.cnblogs.com/shikeyu/p/13368165.html