最小费用最大流

$最小费用最大流$最小费用最大流

题目链接：luogu P3381

题目

如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。

输入

第一行包含四个正整数$N$N、$M$M、$S$S、$T$T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来$M$M行每行包含四个正整数$u_i$ui​、$v_i$vi​、$w_i$wi​、$f_i$fi​，表示第$i$i条有向边从$u_i$ui​出发，到达$v_i$vi​，边权为$w_i$wi​（即该边最大流量为$wi$wi），单位流量的费用为$f_i$fi​。

输出

一行，包含两个整数，依次为最大流量和在最大流量情况下的最小费用。

样例输入

4 5 4 3
4 2 30 2
4 3 20 3
2 3 20 1
2 1 30 9
1 3 40 5

样例输出

50 280

样例解释

如图，最优方案如下：

第一条流为$4-->3$4−−>3，流量为$20$20，费用为$3*20=60$3∗20=60。

第二条流为$4-->2-->3$4−−>2−−>3，流量为$20$20，费用为$（2+1）*20=60$（2+1）∗20=60。

第三条流为$4-->2-->1-->3$4−−>2−−>1−−>3，流量为$10$10，费用为$（2+9+5）*10=160$（2+9+5）∗10=160。

故最大流量为$50$50，在此状况下最小费用为$60+60+160=280$60+60+160=280。

故输出$50\ 280$50 280。

数据范围

对于$30\%$30%的数据：$N<=10$N<=10，$M<=10$M<=10
对于$70\%$70%的数据：$N<=1000$N<=1000，$M<=1000$M<=1000
对于$100\%$100%的数据：$N<=5000$N<=5000，$M<=50000$M<=50000

思路

这道题是一道模板题。
做法就是用$SPFA$SPFA求增广路径，然后增广，就可以了。
其实就是在最大流上面多了个要求最短路径。
不会最大流的看这里：——>点这里<——

代码

#include<queue>
#include<cstdio>
#include<cstring>
#define min(x, y) (x) < (y) ? (x) : (y)

using namespace std;

struct note {
	int to, now, pri, next, op;
}e[100001];
int n, m, s, t, le[5001], x, y, w, f, k, ans1, ans2, dis[5001], run[5001], pre[5001];
bool in[5001];
queue<int>q;

void add(int x, int y, int w, int f) {//连边
	e[++k] = (note){y, w, f, le[x], k + 1}; le[x] = k;
	e[++k] = (note){x, 0, -f, le[y], k - 1}; le[y] = k; 
}

void getan() {
	int now = t;
	while (now != s) {//从汇点开始返回原点
		e[pre[now]].now -= run[t];//更改边的值
		e[e[pre[now]].op].now += run[t];
		now = e[e[pre[now]].op].to;
	}
	
	ans1 += run[t];//加到答案上面
	ans2 += run[t] * dis[t];
}

bool spfa() {
	memset(dis, 0x7f, sizeof(dis));
	memset(pre, 0, sizeof(pre));
	memset(run, 0, sizeof(run));
	memset(in, 0, sizeof(in));
	while (!q.empty()) q.pop();
	int temp = dis[0];
	in[s] = 1;
	dis[s] = 0;
	run[s] = 2147483647;
	
	q.push(s);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
		for (int i = le[now]; i; i = e[i].next)
			if (dis[now] + e[i].pri < dis[e[i].to] && e[i].now) {//费用更小且可以流
				dis[e[i].to] = dis[now] + e[i].pri;
				run[e[i].to] = min(run[now], e[i].now);//维护这条路最多能留多少
				pre[e[i].to] = i;//记录编号，以便之后返回
				
				if (!in[e[i].to]) {
					in[e[i].to] = 1;
					q.push(e[i].to);
				}
			}
		
		in[now] = 0;
	}
	
	if (dis[t] == temp) return 0;
	return 1;
}

int read() {//快读
	int an = 0;
	char c = getchar();
	while (c > '9' || c < '0') c = getchar();
	while (c <= '9' && c >= '0') {
		an = an * 10 + c - 48;
		c = getchar();
	}
	return an;
}

int main() {
	n = read();//输入
	m = read();
	s = read();
	t = read();
	
	for (int i = 1; i <= m; i++) {
		x = read();//输入
		y = read();
		w = read();
		f = read();
		add(x, y, w, f);//连边
	}
	
	while (spfa())//spfa求最小费最大流
		getan();//增值
	
	printf("%d %d", ans1, ans2);//输出
	
	return 0;
}