網絡流24題18. 分配問題

2019-11-06 06:17:38

字體：大中小

來源：轉載

供稿：網友

分配問題

Description

有 n 件工作要分配給 n 個人做。第 i 個人做第 j 件工作產生的效益為cij $c_{ij}$ 。試設計一個將n 件工作分配給 n 個人做的分配方案，使產生的總效益最大。對于給定的 n 件工作和 n 個人，計算最優分配方案和最差分配方案。

Input

第 1 行有 1 個正整數 n，表示有 n 件工作要分配給 n 個人做。接下來的 n 行中，每行有 n 個整數cij $c_{ij}$ ，1≤i≤n，1≤j≤n，表示第 i 個人做第 j 件工作產生的效益為cij $c_{ij}$ 。

Output

輸出計算出的最小總效益和最大總效益。

題解

二分圖匹配問題。建立附加源S，附加匯T。建圖： 1.S向每個人連接一條容量為1，費用為0的邊。 2.每件工作向T連接一條容量為1，費用為0的邊。 3.每個人向每件工作連接一條容量為1，費用為cij $c_{ij}$ 。答案即為最小(大)費用最大流。

#include<cstdio>#include<iostream>#include<cstring>using namespace std;const int N = 1000 + 10, M = 1000000 + 10, inf = 0x3f3f3f3f;struct Edge{ int fr, to, cap, flow, cost;}edg[M];int hd[N], nxt[M], tot;int n, s, t;int d[N], a[N], p[N], q[N], inq[N];int mp[N][N];void insert(int u, int v, int w, int x){ edg[tot].fr = u, edg[tot].to = v, edg[tot].cap = w, edg[tot].flow = 0, edg[tot].cost = x; nxt[tot] = hd[u]; hd[u] = tot; tot++; edg[tot].fr = v, edg[tot].to = u, edg[tot].cap = 0, edg[tot].flow = 0, edg[tot].cost = -x; nxt[tot] = hd[v]; hd[v] = tot; tot++;}bool spfa1(int &fl, int &cst){ for(int i = s; i <= t; i++) d[i] = inf; d[s] = 0; p[s] = 0; a[s] = inf; int head = 0, tail = 1; q[0] = s; inq[s] = 1; while(head != tail){ int u = q[head++]; if(head == 1001) head = 0; inq[u] = 0; for(int i = hd[u]; i >= 0; i = nxt[i]){ Edge &e = edg[i]; if(d[e.to] > d[u] + e.cost && e.cap > e.flow){ d[e.to] = d[u] + e.cost; p[e.to] = i; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]){ q[tail++] = e.to; if(tail == 1001) tail = 0; inq[e.to] = 1; } } } } if(d[t] == inf) return false; fl += a[t]; cst += a[t] * d[t]; int u = t; while(u != s){ edg[p[u]].flow += a[t]; edg[p[u]^1].flow -= a[t]; u = edg[p[u]].fr; } return true;}bool spfa2(int &fl, int &cst){ for(int i = s; i <= t; i++) d[i] = -inf; d[s] = 0; p[s] = 0; a[s] = inf; int head = 0, tail = 1; q[0] = s; inq[s] = 1; while(head != tail){ int u = q[head++]; if(head == 1001) head = 0; inq[u] = 0; for(int i = hd[u]; i >= 0; i = nxt[i]){ Edge &e = edg[i]; if(d[e.to] < d[u] + e.cost && e.cap > e.flow){ d[e.to] = d[u] + e.cost; p[e.to] = i; a[e.to] = min(a[u], e.cap - e.flow); if(!inq[e.to]){ q[tail++] = e.to; if(tail == 1001) tail = 0; inq[e.to] = 1; } } } } if(d[t] == -inf) return false; fl += a[t]; cst += a[t] * d[t]; int u = t; while(u != s){ edg[p[u]].flow += a[t]; edg[p[u]^1].flow -= a[t]; u = edg[p[u]].fr; } return true;}void init(){ scanf("%d", &n); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d", &mp[i][j]);}void build(){ memset(hd, -1, sizeof(hd)); tot = 0; s = 0, t = n * 2 + 1; for(int i = 1; i <= n; i++){ insert(s, i, 1, 0); insert(n + i, t, 1, 0); } for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) insert(i, n + j, inf, mp[i][j]);}void work(){ int flow = 0, cost = 0; build(); while(spfa1(flow, cost));