洛谷P4043 费用流

这题的建图方式可以类比洛谷P1251
我是由那个题才想到这么建的，由于每条边至少经过一次，我们又不清楚需要跑多少次，把边看成点，点与汇点相连，可是我们又不知道最大流应该是多少，直接这么连会发生错误。利用那道题的思想，每条边最少需要一次，那么就每条边看做两个点，点1和点2，点1有1的流量流向汇点，点2接受源点的1的流量，这是一个补流的过程。利用补流的过程和把边拆成两个点，我们就可以跑出来最大流是边数的最小费用。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<bitset>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define ui unsigned int
//ios::sync_with_stdio(false);
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ull unsigned long long
#define endd puts("");
#define re register
#define endl "\n"
#define ll long long
#define double long double
#define il inline
using namespace std;
#define PI  3.1415926535898
const double eqs = 1e-6;
const long long max_ = 1000000 + 7;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const long long INF = 2e18 + 7;
inline int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0'&&ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}
inline void write(int x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
int head[max_], xiann = 2;
struct kk {
	int to, next, flow, val;
	kk() {}
	kk(int to, int next, int flow, int val) :to(to), next(next), flow(flow), val(val) {}
}xian[max_ << 1];
il void add(int a, int b, int c, int d) {
	/*if (c) {
		cout << a << " " << b << " " << c << endl;
	}*/
	xian[xiann] = kk(b, head[a], c, d);
	head[a] = xiann;
	xiann++;
}
int cur[max_], dis[max_], N = 0, que[max_], L, R;
int S, T;
bool vis[max_];
bool spfa() {
	re int i, now, to;
	for (i = 0; i <= N; i++) {
		cur[i] = head[i]; dis[i] = inf; vis[i] = 0;
	}
	L = 1, R = 0;
	que[++R] = S; vis[S] = 1; dis[S] = 0;
	while (L <= R) {
		now = que[L]; L++; vis[now] = 0;
		for (i = head[now]; i; i = xian[i].next) {
			to = xian[i].to;
			if (xian[i].flow  && dis[to] > dis[now] + xian[i].val) {
				dis[to] = dis[now] + xian[i].val;
				if (!vis[to]) {
					vis[to] = 1;
					que[++R] = to;
				}
			}
		}
	}
	return dis[T] != inf;
}
int mincost, maxflow;
int dfs(int now, int flow) {
	if (!flow || now == T)return flow;
	re int  to, tot = 0, f;
	vis[now] = 1;
	for (int &i = cur[now]; i; i = xian[i].next) {
		to = xian[i].to;
		if (!vis[to] && xian[i].flow && dis[to] == dis[now] + xian[i].val && (f = dfs(to, min(flow - tot, xian[i].flow)))) {
			tot += f;
			xian[i].flow -= f; xian[i ^ 1].flow += f;
			mincost += f * xian[i].val;
			if (tot == flow)break;
		}
	}
	vis[now] = 0;
	return tot;
}
void dinic() {
	while (spfa()) {
		maxflow += dfs(S, inf);
	}
}
il void addEdge(int a, int b, int c, int d) {
	//cout << a << " "  << b <<" "<< c << endl;
	add(a, b, c, d);
	add(b, a, 0, -d);
}
vector<pair<int, int> > ask[700];
map<int, pair<int, int> >mp;
il void ini() {
	re int n = read(),i,j,num,cost,to,idn,xianid = 0,nowxianid = 0,a,b;
	pair<int, int> temp;
	idn = n;
	for(i = 1;i <= n;i++){
		num = read();
		for (j = 1; j <= num; j++) {
			to = read(); cost = read();
			ask[i].push_back(make_pair(to, cost));
			++xianid;
			a = ++idn; b = ++idn;
			mp[xianid] = make_pair(a, b);
		}
	}
	S = 0; N = T = ++idn;
	addEdge(S, 1, inf, 0);
	for (i = 1; i <= n; i++) {
		for (auto pa : ask[i]) {
			nowxianid++; 
			temp = mp[nowxianid];
			addEdge(temp.first, temp.second, inf, 0);
			addEdge(temp.first, T, 1, 0);
			addEdge(S,temp.second, 1, 0);
			addEdge(temp.second, pa.first, inf, 0);
			addEdge(i, temp.first, inf, pa.second);
		}
	}
	dinic();
	cout << mincost;
}
signed main() {
	ini();
	return 0;
}

本文地址：https://blog.csdn.net/qq_43804974/article/details/107554692