最小割练习

网络战争

与01分数规划相结合
\(\dfrac{\sum W_e}{|C|} < \lambda\) 对应 \(\sum(W_e - \lambda) < 0\)
二分 \(\lambda\) 找到 \(\dfrac{\sum W_e}{|C|}\) 的最小值
\(W_e - \lambda \le 0\) 的边必选, 剩余的集合内的边一定不选，则边割集与流网络的割相对应， 求一个最小割即可

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 10;
const int M = (400 + 10) * 2;
const int INF = 1e9;
const double eps = 1e-8;

int n, m, S, T;
struct Edge
{
	int to, nxt, w;
	double flow;
}line[M];
int fist[N], idx;
int cur[N], d[N];

void add(int x, int y, int z)
{
	line[idx] = {y, fist[x], z, 0};
	fist[x] = idx ++;
	line[idx] = {x, fist[y], z, 0};
	fist[y] = idx ++; 
}

bool bfs()
{
	queue<int> q;
	memset(d, -1, sizeof d);
	q.push(S), d[S] = 0, cur[S] = fist[S];
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int i = fist[u]; i != -1; i = line[i].nxt)
		{
			int v = line[i].to;
			if(d[v] == -1 && line[i].flow)
			{
				d[v] = d[u] + 1;
				cur[v] = fist[v];
				if(v == T) return 1;
				q.push(v);
			}
		} 
	} 
	return 0;
}

double find(int u, double limit)
{
	if(u == T) return limit;
	double flow = 0;
	for(int i = cur[u]; i != -1 && flow < limit; i = line[i].nxt)
	{
		cur[u] = i;
		int v = line[i].to;
		if(d[v] == d[u] + 1 && line[i].flow)
		{
			double t = find(v, min(line[i].flow, limit - flow));
			if(t < eps) d[v] = -1;
			line[i].flow -= t;
			line[i ^ 1].flow += t;
			flow += t;
		} 
	}
	return flow;
}

double dinic(double mid)
{
	double res = 0;
	for(int i = 0; i < idx; i += 2)
		if(line[i].w <= mid) 
		{
			res += line[i].w - mid;
			line[i].flow = line[i ^ 1].flow = 0; 
		}
		else line[i].flow = line[i ^ 1].flow = line[i].w - mid;
	double r = 0, flow;
	while(bfs()) while(flow = find(S, INF)) r += flow;
	return res + r;
}

int main()
{
	scanf("%d%d%d%d", &n, &m, &S, &T);
	memset(fist, -1, sizeof fist);
	for(int i = 1; i <= m; ++ i)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		add(a, b, c);
	}
	
	double l = 0, r = 1e7, res;
	while(r - l >= eps)
	{
		double mid = (l + r) / 2;
		if(dinic(mid) <= eps) 
		{
			r = mid;
			res = mid;
		}
		else l = mid;
	}
	printf("%.2lf\n", res);
	return 0;
} 

最优标号

最小割练习

原文：https://www.cnblogs.com/ooctober/p/14428071.html