0|1分数规划

标签：分数 int sum db mid 规划 rep define

这种分子上一大坨求和，分母上一大坨求和，然后求最值的问题属于一类特殊的问题。被称为0|1分数规划问题。
也就是\(\frac{\sum{f_i} * w_i} {\sum{g_i} *w_i }\)
找一组\({w_i} \in \{0,1\}\)使上面的式子最小
通常的做法就是二分答案
假设我们要求的是最大值，然后二分一个答案mid,然后推式子

\[\frac{\sum{f_i} * w_i} {\sum{g_i} *w_i }>mid \]

\[{\sum{f_i} * w_i}-mid*{\sum{g_i} *w_i }>0 \]

\[w_i *({\sum{f_i}-mid*g_i})>0 \]

那么只要求出不等号左边的式子的最大值就行了。如果最大值比 0 要大，说明 mid 是可行的，否则不可行

针对于这道题目也是
这里既有边权又有点权，可以把点权下放到出边上
然后上面的式子的含义也就变为了在图上求正环。
正环也可以用spfa来求，只需要和负环对称一下，求最短路变成求最长路即可。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back
#define inf 0x3f3f3f3f*1ll

using namespace std;

void solve()
{
	int n,m;
	cin>>n>>m;
	vector<vector<pii>>g(n+1);
	vector<int>a(n+1);
	rep(i,1,n){
		cin>>a[i];
	}
	rep(i,1,m){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].pb({v,w});
	}	
	auto check=[&](db tar){
		vector<int>inq(n+1,0);
		vector<int>cnt(n+1,0);
		vector<db>d(n+1,0);
		queue<int>q;
		rep(i,1,n){
			q.push(i);
			inq[i]=1;
		}
		while(q.size()){
			auto u=q.front();
			q.pop();
			inq[u]=0;
			for(auto it:g[u]){
				int v=it.x,w=it.y;
				if(d[v]<d[u]+a[u]-w*tar){
					d[v]=d[u]+a[u]-w*tar;
					cnt[v]=cnt[u]+1;
					if(cnt[v]>=n)	return true;
					if(!inq[v]){
						inq[v]=1;
						q.push(v);
					}
				}
			}
		}
		return false;
	};
	db l=0,r=1010;
	while(r-l>1e-5){
		db mid=(l+r)/2;
		if(check(mid))	l=mid;
		else	r=mid;
	}
	//c++默认输出6位精度
	cout<<setiosflags(ios::fixed)<<setprecision(2)<<l<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

标签：分数,int,sum,db,mid,规划,rep,define
From： https://www.cnblogs.com/cxy8/p/18016648