#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 350;
struct Edge { int from, to, cap, flow, cost; };
vector<Edge> edges;
vector<int> G[maxn];
int inque[maxn]; //spfa
int d[maxn]; //源点到当前点的最短路
int p[maxn]; //入弧编号
int a[maxn]; //可改进量
void init(int n)
{
for(int i=0; i<=n; i++) G[i].clear();
edges.clear();
}
void add_edge(int from, int to, int cap, int cost)
{
edges.push_back((Edge){from, to, cap, 0, cost});
edges.push_back((Edge){to, from, 0, 0, -cost});
int m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool spfa(int s, int t, int &flow, long long &cost)
{
memset(d, 0x3f, sizeof(d));
memset(inque, 0, sizeof(inque));
d[s] = 0; inque[s] = 1;
a[s] = inf; p[s] = 0;
queue<int> que;
que.push(s);
while(!que.empty()){
int u = que.front(); que.pop();
inque[u] = 0;
for(int i=0; i<G[u].size(); i++){
Edge e = edges[G[u][i]];
if(e.cap>e.flow && d[e.to]>d[u]+e.cost){
d[e.to] = d[u] + e.cost;
if(!inque[e.to]) que.push(e.to), inque[e.to]=1;
p[e.to] = G[u][i]; //e.to的入弧编号
a[e.to] = min(a[u], e.cap-e.flow); //更新可改进量
}
}
}
if(d[t] == inf) return false;
flow += a[t];
cost += (long long)a[t]*(long long)d[t];
for(int u=t; u!=s; u=edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
}
return true;
}
int MCMF(int s, int t, long long &cost)
{
int flow = 0; cost = 0;
while(spfa(s, t, flow, cost));
return flow;
}
原文链接: https://www.cnblogs.com/xingxing1024/p/5275302.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/230221
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!