[Non] 房屋分配
大意
给定 \(n\) 户村民和 \(n\) 间房，每户对每间房有一个报价，求一个完美匹配，使得匹配的总报价和最大。
思路
这个题实际上是一个二分图最大权匹配，那么我们需要做什么呢？
一共 \(n\) 个人，分 \(n\) 间房子，最大匹配，且有 \(n \times n\) 条边，所以一定能保证一个最大的匹配，那么我们需要考虑的就是如何让费用最大。
我们只需要保证，每个村民只分 1 间房子 且 每间房子只被分配 1 次，那么我们只需要建立源点 \(S\)，由 \(S\) 向每个村民连容量为 \(1\)，费用为 \(0\) 的边，再在村民和房子间连容量为 \(1\)，费用为 \(-w_i\) 的边（因为我们求的是最短路，最后直接取反），在房子和最终的汇点连容量为 \(1\)，费用为 \(0\) 的边，求最小费用最大流即可，最终输出答案取反即可。
代码
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;const int MAX_N = 1000;
const int MAX_M = MAX_N * MAX_N * 2;
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<int> q;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() {freopen("house.in", "r", stdin);freopen("house.out", "w", stdout);int n;init();cin >> n;s = 0, t = 2 * n + 1;for(int i = 1; i <= n; i++) {addedge(s, i, 1, 0);}for(int i = 1; i <= n; i++) {addedge(i + n, t, 1, 0);}for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {int price;cin >> price;addedge(i, j + n, 1, -price);}}cout << -costflow() << endl;return 0;
}