欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

洛谷P4043 费用流

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

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

#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