首页 > 代码库 > [SWUST1753] 分配问题(费用流,最优匹配)
[SWUST1753] 分配问题(费用流,最优匹配)
题目链接:https://www.oj.swust.edu.cn/problem/show/1753
由于每一个人只能做一件工作,所以要在源汇点处设置容量为1费用为0,在二分图中间设置容量为inf。
而不是源点到人处设置容量为inf。
其实就是最优匹配问题,费用流,这样建图之后权值正负各跑一遍就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 typedef struct Node { 6 int u, v, next; 7 LL c, w; 8 }Node; 9 const int maxn = 440; 10 const int maxm = 80010; 11 const LL mod = 0x3f3f3f3fLL; 12 const LL inf = (1LL<<55); 13 int tot, head[maxn]; 14 LL dist[maxn]; 15 LL cost, flow; 16 Node e[maxm]; 17 int pre[maxn]; 18 bool visit[maxn]; 19 queue<int> Q; 20 int S, T, N; 21 22 void init() { 23 S = T = N = 0; 24 memset(head, -1, sizeof(head)); 25 tot = 0; 26 } 27 28 void adde(int u, int v, LL c, LL w) { 29 e[tot].u = u; e[tot].v = v; e[tot].c = c; e[tot].w = w; e[tot].next = head[u]; head[u] = tot++; 30 e[tot].u = v; e[tot].v = u; e[tot].c = 0; e[tot].w = -w; e[tot].next = head[v]; head[v] = tot++; 31 } 32 bool spfa(int s, int t, int n) { 33 int i; 34 for(i = 0; i <= n; i++) { 35 dist[i] = inf; 36 visit[i] = 0; 37 pre[i] = -1; 38 } 39 while(!Q.empty()) Q.pop(); 40 Q.push(s); 41 visit[s] = true; 42 dist[s] = 0; 43 pre[s] = -1; 44 while(!Q.empty()) { 45 int u = Q.front(); 46 visit[u] = false; 47 Q.pop(); 48 for(int j = head[u]; j != -1; j = e[j].next) { 49 if(e[j].c > 0 && dist[u] + e[j].w < dist[e[j].v]) { 50 dist[e[j].v] = dist[u] + e[j].w; 51 pre[e[j].v] = j; 52 if(!visit[e[j].v]) { 53 Q.push(e[j].v); 54 visit[e[j].v] = true; 55 } 56 } 57 } 58 } 59 if(dist[t] == inf) return false; 60 else return true; 61 } 62 LL ChangeFlow(int t) { 63 LL det = mod; 64 int u = t; 65 while(~pre[u]) { 66 u = pre[u]; 67 det = min(det, e[u].c); 68 u = e[u].u; 69 } 70 u = t; 71 while(~pre[u]) { 72 u = pre[u]; 73 e[u].c -= det; 74 e[u ^ 1].c += det; 75 u = e[u].u; 76 } 77 return det; 78 } 79 LL MinCostFlow(int s, int t, int n) { 80 LL mincost, maxflow; 81 mincost = maxflow = 0; 82 while(spfa(s, t, n)) { 83 LL det = ChangeFlow(t); 84 mincost += det * dist[t]; 85 maxflow += det; 86 } 87 cost = mincost; 88 flow = maxflow; 89 return mincost; 90 } 91 92 int n; 93 int w[maxn][maxn]; 94 95 int main() { 96 // freopen("in", "r", stdin); 97 while(~scanf("%d", &n)) { 98 init(); 99 S = 0, T = n * 2 + 1, N = T + 1; 100 for(int i = 1; i <= n; i++) { 101 adde(S, i, 1, 0); 102 adde(i+n, T, 1, 0); 103 for(int j = 1; j <= n; j++) { 104 scanf("%d", &w[i][j]); 105 adde(i, j+n, inf, w[i][j]); 106 } 107 } 108 cout << MinCostFlow(S, T, N) << endl; 109 init(); 110 S = 0, T = n * 2 + 1, N = T + 1; 111 for(int i = 1; i <= n; i++) { 112 adde(S, i, 1, 0); 113 adde(i+n, T, 1, 0); 114 for(int j = 1; j <= n; j++) { 115 adde(i, j+n, inf, -w[i][j]); 116 } 117 } 118 cout << -MinCostFlow(S, T, N) << endl; 119 } 120 return 0; 121 }
[SWUST1753] 分配问题(费用流,最优匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。