P6577 【模板】二分图最大权完美匹配
大意
二分图最大权匹配。
思路
首先，我们先不考虑最大权的问题，我们先考虑如何用网络流解决二分图最大匹配问题，首先，我们考虑这样的事，我们如果想让最小割等于最大匹配，实际上最小割很形象的解决了这个问题，最小割的过程，就是把一张图，割为 \(S\) 与 \(T\) 两部分，那么我们只需要在边 \(u\) 与 \(v\) 间连一条长度为 \(1\) 的边，那么割掉的花费就是 \(1\)。
由于每个点都可以做匹配，只需要把超级原点 \(S\) 连向二分图左边的点即可，二分图右边的点连向 \(T\)，容量都为 \(1\)，这样求出来的最小割就是使得图二分开的最大匹配方案。
那么如果带权呢？那么我们只需要把花费也建出来即可，这样就完成了此题。
但是由于题目只支持 KM 做法，因此此做法仅作为拓展。
代码
//费用流
include
include <string.h>
include
using namespace std;
const int MAX_N = 1000;
const int MAX_M = 10000;
const int inf = 0x3f3f3f3f;
struct edge {
int v, c, w, next;
} e[MAX_M];
int p[MAX_N], s, t, eid;
void init() {
memset(p, -1, sizeof(p));
eid = 0;
}
void insert(int u, int v, int c, int w) {
e[eid].v = v;
e[eid].c = c;
e[eid].w = w;
e[eid].next = p[u];
p[u] = eid++;
}
void addedge(int u, int v, int c, int w) {
insert(u, v, c, w);
insert(v, u, 0, -w);
}
bool vis[MAX_N];
int d[MAX_N];
int pre[MAX_N];
bool spfa() {
memset(vis, 0, sizeof(vis));
memset(d, 0x3f, sizeof(d));
memset(pre, -1, sizeof(pre));
d[s] = 0;
vis[s] = true;
queue
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false;
for (int i = p[u]; i != -1; i = e[i].next) {
if (e[i].c) {
int v = e[i].v;
if (d[u] + e[i].w < d[v]) {
d[v] = d[u] + e[i].w;
pre[v] = i;
if (!vis[v]) {
q.push(v);
vis[v] = true;
}
}
}
}
}
return pre[t] != -1;
}
int costflow() {
int ret = 0;
while(spfa()) {
int flow = inf;
for(int i = t; i != s; i = e[pre[i]^1].v) {
flow = min(e[pre[i]].c, flow);
}
for(int i = t; i != s; i = e[pre[i]^1].v) {
e[pre[i]].c -= flow;
e[pre[i]^1].c += flow;
ret += e[pre[i]].w * flow;
}
}
return ret;
}
int main() {
int n, m;
init();
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
addedge(u, v, 1, -w);
}
s = 0; t = 2 * n + 1;
for(int i = 1;i <= n;i ++){
addedge(s, i, 1, 0);
addedge(n + i, t, 1, 0);
}
cout << -costflow() << endl;
return 0;
}
//KM
include
include
include <string.h>
using namespace std;
typedef long long ll;
const int N = 505;
const ll INF = 1e18;
int n, m;
ll w[N][N], lx[N], ly[N], slack[N];
int rmatch[N], pre[N];
bool rvis[N];
void bfs(int u) {
int x, y = 0, nexty;
ll dt;
memset(pre, 0, sizeof(pre));
for (int i = 1; i <= n; i++) slack[i] = INF;
rmatch[0] = u;
do {rvis[y] = true;x = rmatch[y];dt = INF;for (int i = 1; i <= n; i++) {if (!rvis[i]) {if (slack[i] > lx[x] + ly[i] - w[x][i]) {slack[i] = lx[x] + ly[i] - w[x][i];pre[i] = y;}if (slack[i] < dt) {dt = slack[i];nexty = i;}}}for (int i = 0; i <= n; i++) {if (rvis[i]) {lx[rmatch[i]] -= dt;ly[i] += dt;} else {slack[i] -= dt;}}y = nexty;
} while (rmatch[y] != 0);while (y) {rmatch[y] = rmatch[pre[y]];y = pre[y];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {w[i][j] = -INF;}
}for (int i = 0; i < m; i++) {int u, v; ll c;cin >> u >> v >> c;w[u][v] = max(w[u][v], c);
}for (int i = 1; i <= n; i++) {memset(rvis, 0, sizeof(rvis));bfs(i);
}ll res = 0;
for (int i = 1; i <= n; i++) res += lx[i] + ly[i];cout << res << "\n";
for (int i = 1; i <= n; i++) {cout << rmatch[i] << (i == n ? "" : " ");
}return 0;
}