# Luogu3381 最小费用最大流【模板】

## 输入输出样例

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

### 说明

（BYX：最后两个点改成了1200ms）

### 链接

https://www.luogu.org/problemnew/show/P3381

### 代码

• 1492ms /  4.15MB  代码：2.38KB
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 10010; // 点数
const int maxm = 100010; // 边数
const int inf = 0x3f3f3f3f;

struct Edge
{
int to, next, cap, flow, cost;
}edge[maxm];

int n, m, tot;
bool vis[maxn];

void init()
{
tot = 0;
}

void addedge(int u, int v, int cap, int cost) // 链式前向星存图
{
edge[tot].to = v;
edge[tot].cap = cap;
edge[tot].cost = cost;
edge[tot].flow = 0;
}

bool spfa(int s, int t) // spfa寻找最小费用增广路
{
queue <int> Q;
for (int i = 1; i <= n; ++i)
{
dis[i] = inf;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
Q.push(s);
while (!Q.empty())
{
int u = Q.front();
Q.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost)
{
//                cout << i << " " << u << " " << v << endl;
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if (!vis[v])
{
vis[v] = true;
Q.push(v);
}
}
}
}
if (pre[t] == -1)
return false;
return true;
}

int minCostMaxflow(int s, int t, int &mincost) // 计算费用
{
int maxflow = 0;
mincost = 0;
while (spfa(s, t))
{
int Min = inf;
for (int i = pre[t]; i != -1; i = pre[edge[i^1].to]) // 每次增加的流量
Min = min(Min, edge[i].cap - edge[i].flow);
for (int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
mincost += edge[i].cost * Min;
}
maxflow += Min;
}
return maxflow;
}

int main()
{
int u, v, cost, cap, s, t;
while (scanf("%d%d%d%d", &n, &m, &s, &t) == 4)
{
init();
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d%d", &u, &v, &cap, &cost);
}
int maxflow, mincost = 0;
maxflow = minCostMaxflow(s, t, mincost);
cout << maxflow << " " << mincost << endl;
}
return 0;
}

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

The end.
2018-07-30 星期一