最小费用最大流（洛谷-P3381）

本文主要是介绍最小费用最大流（洛谷-P3381），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

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

输出样例#1：

50 280

思路：最小费用最大流模版题，利用 zkw 费用流解决

源代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<LL,LL>
LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; }
LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;}
LL quickPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;}
LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); }
LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); }
LL LCM(LL x,LL y){ return x/GCD(x,y)*y; }
const double EPS = 1E-10;
const int MOD = 998244353;
const int N = 500000+5;
const int dx[] = {-1,1,0,0,1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;struct Edge {int to;int next;int cap, cost;
} edge[N];
int head[N], tot;
bool vis[N];
int dis[N], level[N];void addEdge(int x, int y, int cap, int cost) {edge[++tot].to = y;edge[tot].next = head[x];edge[tot].cap = cap;edge[tot].cost = cost;head[x] = tot;edge[++tot].to = x;edge[tot].next = head[y];edge[tot].cap = 0;edge[tot].cost = -cost;head[y] = tot;
}bool SPFA(int S, int T, int n) {memset(dis, INF, sizeof(dis));memset(vis, false, sizeof(vis));memset(level, 0, sizeof(level));dis[S] = 0;level[S] = 1;vis[S] = true;deque<int> Q;Q.push_back(S);while (!Q.empty()) {int x = Q.front();Q.pop_front();vis[x] = false;for (int i = head[x]; i != -1; i = edge[i].next) {int to = edge[i].to;if (dis[to] > dis[x] + edge[i].cost && edge[i].cap > 0) {dis[to] = dis[x] + edge[i].cost;level[to] = level[x] + 1;if (!vis[to]) {vis[to] = true;if (!Q.empty() && dis[to] < dis[Q.front()])Q.push_front(to);elseQ.push_back(to);}}}}return dis[T] != dis[n + 1];
}bool flag = false;
int dfs(int x, int T, int t, int &flow, int &cost) {if (x == T) {flow += t;flag = true;return t;}int num = 0, newFlow = 0;for (int i = head[x]; i != -1; i = edge[i].next) {int to = edge[i].to;if (t == num)break;if (dis[x] + edge[i].cost == dis[to] && level[x] + 1 == level[to] && edge[i].cap > 0) {newFlow = dfs(to, T, min(t - num, edge[i].cap), flow, cost);num += newFlow;cost += newFlow * edge[i].cost;edge[i].cap -= newFlow;edge[i ^ 1].cap += newFlow;}}return num;
}
void zkw(int S, int T, int n) {int flow = 0, cost = 0;while (SPFA(S, T, n)) {flag = true;while (flag) {flag = false;dfs(S, T, INF, flow, cost);}}printf("%d %d\n", flow, cost);
}int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {memset(head, -1, sizeof(head));tot = 1;int S, T;scanf("%d%d", &S, &T);for (int i = 1; i <= m; i++) {int x, y, cap, cost;scanf("%d%d%d%d", &x, &y, &cap, &cost);addEdge(x, y, cap, cost);}zkw(S, T, n);}return 0;
}

 

这篇关于最小费用最大流（洛谷-P3381）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---