图论专题I
?
[pku2396 Budget]帶源匯的上下界最大流
From:http://poj.org/problem?id=2396
?
#include <algorithm> #include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <queue> #include <stack> #include <functional> using namespace std; #define N 205+25 #define M 25 #define oo 0x6fffffff #define nil (-1) int cap[N][N], flow[N][N], d[N], fa[N], low[N][N], high[N][N], in[N], out[N], maxflow, _S, _T, S, T; void Init(int n, int m){S = 0, T = n+m+1; _S = n+m+2; _T = n+m+3;memset(in, 0, sizeof(in));memset(out, 0, sizeof(out));memset(flow, 0, sizeof(flow));memset(cap, 0, sizeof(cap));memset(low, 0, sizeof(low));memset(high, 0, sizeof(high));for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j) high[i][j+n] = oo; } bool Bfs(int s, int t, int n){for (int i = 0; i <= n; ++i) d[i] = oo, fa[i] = nil;queue<int> Q;d[s] = 0; Q.push(s);while ( !Q.empty() ){int u = Q.front(); Q.pop();for (int v = 0; v <= n; ++v){if ( cap[u][v] > 0 && d[v] == oo ){d[v] = d[u] + 1; fa[v] = u;if ( v == t ) return true;Q.push(v);}}}return false; } int Dfs(int u, int s, int t, int n, int& maxflow){if ( u != t ){for (int v = 0; v <= n; ++v){if ( cap[u][v] > 0 && d[v] == d[u] + 1 ){int r = Dfs(v, s, t, n, maxflow);if ( r != nil && r != u ) return r;}}d[u] = oo;} else {int cf = oo, r = fa[t];for (int i = t; i != s; i = fa[i]) cf = min(cf, cap[fa[i]][i]);maxflow += cf;for (int i = t; i != s; i = fa[i]){cap[fa[i]][i] -= cf; cap[i][fa[i]] += cf;flow[fa[i]][i] += cf; flow[i][fa[i]] -= cf;if ( !cap[fa[i]][i] ) r = fa[i];}return r;}return nil; } int Dinic(int s, int t, int n){int maxflow = 0;while ( Bfs(s, t, n) ) Dfs(s, s, t, n, maxflow);return maxflow; } void Run(int n, int m){int sum = 0;for (int i = 0; i <= n+m+1; ++i){for (int j = 0; j <= n+m+1; ++j){cap[i][j] = high[i][j] - low[i][j];in[j] += low[i][j]; out[i] += low[i][j];}}for (int i = 0; i <= n+m+1; ++i){int diff = in[i] - out[i];if ( diff >= 0 ) cap[_S][i] = diff, sum += diff;else if ( diff < 0 ) cap[i][_T] = -diff;}cap[T][S] = oo;if ( Dinic(_S, _T, n+m+3) != sum ) {puts("IMPOSSIBLE\n");return;}cap[T][S] = cap[S][T] = 0;Dinic(S, T, n+m+1);for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j){printf("%d ", flow[i][j+n]+low[i][j+n]);}printf("\n");} } int main() {int n,m,ca;scanf("%d", &ca);while ( ca-- ){scanf("%d%d", &n, &m);Init(n, m);int dd;for (int i = 1; i <= n; ++i){scanf("%d", &dd);low[S][i] = high[S][i] = dd;}for (int i = 1; i <= m; ++i){scanf("%d", &dd);low[i+n][T] = high[i+n][T] = dd;}int cc;scanf("%d", &cc);while ( cc-- ){char op;int I, J;scanf("%d %d %c %d", &I, &J, &op, &dd);if ( !I && J != 0 ){for (int i = 1; i <= n; ++i){if ( '<' == op ) high[i][J+n] = min(high[i][J+n], dd-1);else if ( '>' == op ) low[i][J+n] = max(low[i][J+n], dd+1);else if ( '=' == op ) high[i][J+n] = low[i][J+n] = dd;}} else if ( I != 0 && !J ){for (int j = 1; j <= m; ++j){if ( '<' == op ) high[I][j+n] = min(high[I][j+n], dd-1);else if ( '>' == op ) low[I][j+n] = max(low[I][j+n], dd+1);else if ( '=' == op ) high[I][j+n] = low[I][j+n] = dd;}} else if ( !I && !J ){for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j){if ( '<' == op ) high[i][j+n] = min(high[i][j+n], dd-1);else if ( '>' == op ) low[i][j+n] = max(low[i][j+n], dd+1);else if ( '=' == op ) high[i][j+n] = low[i][j+n] = dd;}} else {if ( '<' == op ) high[I][J+n] = min(high[I][J+n], dd-1);else if ( '>' == op ) low[I][J+n] = max(low[I][J+n], dd+1);else if ( '=' == op ) high[I][J+n] = low[I][J+n] = dd;}}Run(n, m);printf("\n");}return 0; } View Code?
[zoj2314?Reactor Cooling]無源匯的上下界可行流
From:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1314
#include <algorithm> #include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <queue> #include <stack> #include <functional> using namespace std; #define N 205 #define M 25 #define oo 0x6fffffff #define nil (-1) queue<pair<int,int> > E; int cap[N][N], flow[N][N], d[N], fa[N], low[N][N], high[N][N], in[N], out[N], _S, _T, maxflow; void Init(int n){_S = 0, _T = n;for (int i = 0; i <= n; ++i)for (int j = 0; j <= n; ++j){in[i] = out[i] = 0;cap[i][j] = 0; flow[i][j] = 0;low[i][j] = oo; high[i][j] = oo;}while ( !E.empty() ) E.pop(); } bool Bfs(int n){for (int i = 0; i <= n; ++i) d[i] = oo, fa[i] = nil;queue<int> Q;d[_S] = 0; Q.push(_S);while ( !Q.empty() ){int u = Q.front(); Q.pop();for (int v = 0; v <= n; ++v){if ( cap[u][v] > 0 && d[v] == oo ){d[v] = d[u] + 1; fa[v] = u;if ( v == _T ) return true;Q.push(v);}}}return false; } int Dfs(int u, int n){if ( u != _T ){if ( d[u] != oo ){for (int v = 0; v <= n; ++v){if ( cap[u][v] > 0 && d[v] == d[u] + 1 ){int r = Dfs(v, n);if ( r != nil && r != u ) return r;}}d[u] = oo;}} else {int cf = oo, r = fa[_T];for (int i = _T; i != _S; i = fa[i]) cf = min(cf, cap[fa[i]][i]);maxflow += cf;for (int i = _T; i != _S; i = fa[i]){cap[fa[i]][i] -= cf; cap[i][fa[i]] += cf;flow[fa[i]][i] += cf; flow[i][fa[i]] -= cf;if ( !cap[fa[i]][i] ) r = fa[i];}return r;}return nil; } int Dinic(int n){maxflow = 0;while ( Bfs(n) ) Dfs(_S, n);return maxflow; } void Run(int n){for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j){if ( high[i][j] == oo || low[i][j] == oo ) continue;cap[i][j] = high[i][j] - low[i][j];in[j] += low[i][j]; out[i] += low[i][j];}int sum = 0;for (int i = 1; i <= n; ++i){int diff = in[i] - out[i];if ( diff > 0 ) cap[_S][i] = diff, sum += diff;else if ( diff < 0 ) cap[i][_T] = -diff;}if ( sum != Dinic(n+1) ){printf("NO\n");} else {printf("YES\n");while ( !E.empty() ){pair<int,int> e = E.front(); E.pop();printf("%d\n", flow[e.first][e.second]+low[e.first][e.second]);}} } int main() {int n,m, ca;scanf("%d", &ca);while ( ca-- ){scanf("%d%d", &n, &m);Init(n+1);for (int i = 0; i < m; ++i){int I, J, l, c;scanf("%d%d%d%d", &I, &J, &l, &c);low[I][J] = l; high[I][J] = c;E.push(make_pair(I,J));}Run(n);printf("\n");}return 0; } View Code?
[noi 志愿者招募]帶源匯的上下界費用流
From:http://www.lydsy.com/JudgeOnline/problem.php?id=1061
Solution:
差分, 流守恒性, 容量限制(https://www.byvoid.com/blog/noi-2008-employee)
#include <algorithm> #include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <queue> #include <stack> #include <functional> using namespace std; #define N 1005 #define M 10005 #define oo 0x7fffffff #define nil (-1) bool inQ[N]; struct { int w,c; int to,ba,next; } nod[N*2+2*M]; int adj[N], d[N], fa[N], idx[N], in[N], now, S, T; void Init(int n, int m){now = 0;S = 0; T = n+2;for (int i = 0 ; i <= n+2; ++i) adj[i] = nil, in[i] = 0; } int NewNode(int u, int w, int c){nod[++now].to = u; nod[now].w = w; nod[now].c = c; nod[now].next = nil;return now; } void AddEdge(int u, int v, int w, int c){int u1 = NewNode(v, w, c);int v1 = NewNode(u, -w, 0);nod[u1].ba = v1; nod[v1].ba = u1;nod[u1].next = adj[u]; adj[u] = u1;nod[v1].next = adj[v]; adj[v] = v1; } bool Spfa(int s, int t, int n){for (int i = 0; i <= n; ++i) d[i] = oo, fa[i] = nil, inQ[i] = false;queue<int> Q;d[s] = 0; Q.push(s); inQ[s] = true;while ( !Q.empty() ){int u = Q.front(); Q.pop(); inQ[u] = false;for (int i = adj[u]; i != nil; i = nod[i].next){int v = nod[i].to;if ( nod[i].c > 0 && d[v] - d[u] > nod[i].w ){d[v] = d[u] + nod[i].w; fa[v] = u; idx[v] = i;if ( !inQ[v] ) inQ[v] = true, Q.push(v);}}}return d[t] != oo; } int Argument(int s, int t){int cf = oo;for (int i = t; i != s; i = fa[i]) cf = min(cf, nod[idx[i]].c);for (int i = t; i != s; i = fa[i]){nod[idx[i]].c -= cf; nod[nod[idx[i]].ba].c += cf;}return cf * d[t]; } int MinCost_Flow(int s, int t, int n){int ans = 0;while ( Spfa(s, t, n) ) ans += Argument(s, t);return ans; } void RunTest(int n, int m){Init(n, m);for (int i = 1; i <= n; ++i){int cc;scanf("%d", &cc);in[i] -= cc; in[i+1] += cc;AddEdge(i, i+1, 0, oo-cc);}for (int i = 1; i <= m; ++i){int sd, td, cc;scanf("%d%d%d", &sd, &td, &cc);AddEdge(td+1, sd, cc, oo);}for (int i = 1; i <= n+1; ++i){if ( in[i] > 0 ) AddEdge(S, i, 0, in[i]);else AddEdge(i, T, 0, -in[i]);}printf("%d\n", MinCost_Flow(S, T, n+2)); } int main() {int n, m;while ( scanf("%d%d", &n, &m) != EOF ){RunTest(n, m);}return 0; } View Code?
[vijos 80人環游世界]帶源匯的上下界費用流
From:https://www.vijos.org/p/1213
Solution:
這題把我快搞殘了,最容易想到的是拆點,然后容量上下界為V; 然后, 需要注意的兩個點：
1.每個人都可能從任何一個城市出發, 所以要用一個點S連接所有城市, 容量為oo,再用一個超級源點SS連接S,容量為m。
2.最終m個人可能停留在M(M<=m)個城市, 所以還要把停留在的城市的流量引導超級匯點TT去。
綜合1,2及容量上下界, 就變成m個流量走到匯點并保證m個城市恰好經過。
#include <algorithm> #include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <queue> #include <stack> #include <functional> using namespace std; #define N 205 #define M 10005 #define oo 0x7fffffff #define nil (-1) bool inQ[N]; struct { int w,c; int to,ba,next; } nod[N*N]; int adj[N], d[N], fa[N], idx[N], in[N], now, S, T, _S, _T; void Init(int n, int m){now = 0;S = 2*n+1; T = 2*n+2; _S = 2*n+3; _T = 2*n+4;for (int i = 0 ; i <= 2*n+4; ++i) adj[i] = nil, in[i] = 0; } int NewNode(int u, int w, int c){nod[++now].to = u; nod[now].w = w; nod[now].c = c; nod[now].next = nil;return now; } void AddEdge(int u, int v, int w, int c){int u1 = NewNode(v, w, c);int v1 = NewNode(u, -w, 0);nod[u1].ba = v1; nod[v1].ba = u1;nod[u1].next = adj[u]; adj[u] = u1;nod[v1].next = adj[v]; adj[v] = v1; } bool Spfa(int s, int t, int n){for (int i = 0; i <= n; ++i) d[i] = oo, fa[i] = nil, inQ[i] = false;queue<int> Q;d[s] = 0; Q.push(s); inQ[s] = true;while ( !Q.empty() ){int u = Q.front(); Q.pop(); inQ[u] = false;for (int i = adj[u]; i != nil; i = nod[i].next){int v = nod[i].to;if ( nod[i].c > 0 && d[v] - d[u] > nod[i].w ){d[v] = d[u] + nod[i].w; fa[v] = u; idx[v] = i;if ( !inQ[v] ) inQ[v] = true, Q.push(v);}}}return d[t] != oo; } int Argument(int s, int t){int cf = oo;for (int i = t; i != s; i = fa[i]) cf = min(cf, nod[idx[i]].c);for (int i = t; i != s; i = fa[i]){nod[idx[i]].c -= cf; nod[nod[idx[i]].ba].c += cf;}return cf*d[t]; } int MinCost_Flow(int s, int t, int n){int ans = 0;while ( Spfa(s, t, n) ) ans += Argument(s, t);return ans; } void RunTest(int n, int m){Init(n, m);for (int i = 1; i <= n; ++i){int cc;scanf("%d", &cc);in[i] -= cc; in[i+n] += cc;AddEdge(0, i, 0, oo);AddEdge(i+n, T, 0, cc);}for (int i = 1; i <= n; ++i)for (int j = 1; j <= n-i; ++j){int cc;scanf("%d", &cc);if ( cc != -1 ) AddEdge(i+n, i+j, cc, oo);}for (int i = 0; i <= 2*n+2; ++i){if ( in[i] > 0 ) AddEdge(_S, i, 0, in[i]);else AddEdge(i, _T, 0, -in[i]);}AddEdge(S, 0, 0, m);AddEdge(T, S, 0, oo);printf("%d\n", MinCost_Flow(_S, _T, 2*n+4)); } int main() {int n, m;while ( scanf("%d%d", &n, &m) != EOF ){RunTest(n, m);}return 0; } View Code?
[vijos 最大獲利]最大流
From:https://www.vijos.org/p/1352
Solution:
和算法導論的思考題差不多,源點連接基站, 匯點連接用戶, 若用戶i使用基站a,b, 則a,b分別連接i, 容量oo。可以證明, 對任意的有限容量割(S,T), 對用戶i屬于T, 若基站j與i連接, 則基站j屬于T。
反證法: 假設j不屬于T, 那么j屬于S, 且(j,i)容量為oo, 即S可到i, 與i屬于T矛盾。
由此可以得出: 一旦i被選中, 與i關聯的基站都被選中。
再計算兩個式子: 1.C[S,T]; 2.利潤M = sigma(Custom[i]) - sigma(Base[i]), 其中Custom[i]是從T可達的用戶(表明被選中), Base[i]是從T可達的基站(表明被選中)
聯合1,2即得 利潤M = TotalCustom - C[S,T]（TotalCustom是所有用戶的費用）
#include <algorithm> #include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <queue> #include <stack> #include <functional> using namespace std; #define N 500005 #define M 10005 #define oo 0x7fffffff #define nil (-1) struct { int c,to,ba,next; } nod[N*4]; int adj[N], d[N], idx[N], fa[N], maxflow, now, S, T; void Init(int n){now = 0; S = 0; T = n;for (int i = 0; i <= n; ++i) adj[i] = nil; } int NewNode(int u, int c){nod[++now].c = c; nod[now].to = u; nod[now].next = nil;return now; } void AddEdge(int u, int v, int c){int u1 = NewNode(v, c);int v1 = NewNode(u, 0);nod[u1].ba = v1; nod[v1].ba = u1;nod[u1].next = adj[u]; adj[u] = u1;nod[v1].next = adj[v]; adj[v] = v1; } bool Bfs(int n){for (int i = 0; i <= n; ++i) d[i] = oo, fa[i] = nil;queue<int> Q;d[S] = 0; Q.push(S);while( !Q.empty() ){int u = Q.front(); Q.pop();for (int i = adj[u]; i != nil ; i = nod[i].next){int v = nod[i].to;if ( nod[i].c > 0 && d[v] == oo ){d[v] = d[u] + 1;if ( v == T ) return true;Q.push(v);}}}return false; } int Dfs(int u){if ( u != T ){if ( d[u] != oo ){for (int i = adj[u]; i != nil; i = nod[i].next){int v = nod[i].to;if ( nod[i].c > 0 && d[v] == d[u]+1 ){fa[v] = u; idx[v] = i;int r = Dfs(v);if ( r != nil && r != u ) return r;}}d[u] = oo;}} else {int cf = oo, r = fa[T];for (int i = T; i != S; i = fa[i]) cf = min(cf, nod[idx[i]].c);maxflow += cf;for (int i = T; i != S; i = fa[i]){nod[idx[i]].c -= cf; nod[nod[idx[i]].ba].c += cf;if ( !nod[idx[i]].c ) r = fa[i];}return r;}return nil; } int Dinic(int n){maxflow = 0;while ( Bfs(n) ) Dfs(S);return maxflow; } void RunTest(int n, int m){Init(n+m+1);for (int i = 1; i <= n; ++i){int cc;scanf("%d", &cc);AddEdge(S, i, cc);}int sum = 0;for (int i = 1; i <= m; ++i){int a,b,cc;scanf("%d%d%d", &a, &b, &cc);AddEdge(a, n+i, oo);AddEdge(b, n+i, oo);AddEdge(n+i, T, cc);sum += cc;}printf("%d\n", sum - Dinic(n+m+1)); } int main() {int n,m;while( scanf("%d%d", &n, &m) != EOF ) RunTest(n,m);return 0; } View Code?
[vijos 炸毀燃料庫]最大費用流
From:https://www.vijos.org/p/1499
Solution:
這題建圖建到吐血。思路和志愿者招募差不多,差分,流守恒。第i桶燃料記為X[i]。然后,記P[i]為第i個連續區間覆蓋下可選燃料的約束。舉個例子:
6 5 3
2 3 4 2 1 3
這里只有兩個連續區間, 分別是[1,5], [2,6], 然后它們要滿足:
P[1] = X[1] + X[2] + X[3] + X[4] + X[5] <= 3
P[2] = X[2] + X[3] + X[4] + X[5] + X[6] <= 3
引入松弛變量Y[I]>=0, 變成如下形式:
P[1] = X[1] + X[2] + X[3] + X[4] + X[5] + Y[1] = 3
P[2] =?X[2] + X[3] + X[4] + X[5] + X[6] + Y[2] = 3
引入P[0] = P[3] = 0, 差分:
P[1] - P[0] =?X[1] + X[2] + X[3] + X[4] + X[5] + Y[1] = 3
P[2] - P[1] = X[6] - X[1] + Y[2] - Y[1] = 0
P[3] - P[2] = -X[2] - X[3] - X[4] - X[5] - X[6] - Y[2] = -3
我們再把式子變下形:
X[1] + X[2] + X[3] + X[4] + X[5] + Y[1] - 3 = 0
X[6] - X[1] + Y[2] - Y[1] = 0
-X[2] - X[3] - X[4] - X[5] - X[6] - Y[2] + 3 = 0
可以觀察, 三個式子和網絡流的流守恒很像, 其中X,Y就是流量, 負的表示流出, 正的表示流入, 而負常數表示從源點流出, 正常數表示流入匯點。因此, 嘗試用3個等式建立網絡流, 每個等式代表一個頂點, 然后從X[i](等式I)到-X[i](等式J)指向邊,容量為1, 從Y[i](等式I)到-Y[i](等式J)指向邊,容量為oo。再求最大費用流即可。
#include <algorithm> #include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <queue> #include <vector> #include <functional> using namespace std; #define N 1005 #define M 105 #define oo 0x6fffffff #define nil (-1) struct {int w,c,to,ba,next;} nod[N*N]; bool inQ[N]; vector<int> P[N]; int adj[N], d[N], fa[N], idx[N], v[N], now, S, T; void Init(int n, int m){now = 0; S = 0; T = n-m+3;for (int i = 0; i <= n-m+3; ++i) adj[i] = nil, P[i].clear(); } int NewNode(int u, int w, int c){nod[++now].to = u; nod[now].c = c; nod[now].w = w; nod[now].next = nil;return now; } void AddEdge(int u, int v, int w, int c){int u1 = NewNode(v, w, c);int v1 = NewNode(u, -w, 0);nod[u1].ba = v1; nod[v1].ba = u1;nod[u1].next = adj[u]; adj[u] = u1;nod[v1].next = adj[v]; adj[v] = v1; } bool Spfa(int n){for (int i = 0; i <= n; ++i) d[i] = -oo, fa[i] = nil, inQ[i] = false;queue<int> Q;d[S] = 0; Q.push(S); inQ[S] = true;while ( !Q.empty() ){int u = Q.front(); Q.pop(); inQ[u] = false;for (int i = adj[u]; i != nil; i = nod[i].next){int v = nod[i].to;if ( nod[i].c > 0 && d[v] < d[u] + nod[i].w ){fa[v] = u; idx[v] = i;d[v] = d[u] + nod[i].w;if ( !inQ[v] ) inQ[v] = true, Q.push(v);}}}return d[T] != -oo; } int Argument(){int cf = oo;for (int i = T; i != S; i = fa[i]) cf = min(cf, nod[idx[i]].c);for (int i = T; i != S; i = fa[i]){nod[idx[i]].c -= cf; nod[nod[idx[i]].ba].c += cf;}return d[T]; } int MinCost_Flow(int n){int cost = 0;while ( Spfa(n) ) cost += Argument();return cost; } void RunTest(int n, int m, int k){Init(n, m);int tot = 1;for (int i = 1; i < n-m+2; ++i) AddEdge(i, i+1, 0, oo);for (int i = 1; i <= n; ++i){scanf("%d", v+i);if ( i <= m ){P[tot].push_back(i);} else {++tot;P[tot].push_back(i);P[tot].push_back(m-i);}}++tot;for (int i = n-m+1; i <= n; ++i) P[tot].push_back(-i);for (int i = 1; i <= tot; ++i)for (int j = 0; j < (int)P[i].size(); ++j){for (int k1 = i + 1; k1 <= tot; ++k1)for (int k2 = 0; k2 < (int)P[k1].size(); ++k2){if ( P[i][j] == - P[k1][k2] ){AddEdge(i, k1, v[P[i][j]], 1);}}}AddEdge(S, 1, 0, k); AddEdge(n-m+2, T, 0, k);printf("%d\n", MinCost_Flow(n-m+3)); } int main() {int n,m,k;while( scanf("%d%d%d", &n, &m, &k) != EOF ) RunTest(n,m,k);return 0; } View Code?
[vijos 跳舞]最大流
From:https://www.vijos.org/p/1521
Solution:
當不能解所提題目時, 盡量回憶和之有關的問題, 嘗試丟棄或改變條件。如果不考慮k, 那么這個問題就是求能有幾次完全匹配。這個問題怎么解決?按最大流方式建圖, 只能求一次最大匹配(判斷是否是完全匹配)。不難發現,一旦是完全匹配, 那么與源匯連接的邊都是0容量, 于是, 我們可以在此基礎上, 再給源匯連接的邊補上1容量, 繼續求最大流, 直到找不出完全匹配的最大流, 就是答案。
現在, 如何求有幾次完全匹配的問題我們解決了。在此考慮k, 注意題目提到, 不管男孩女孩最多只和k個不喜歡的跳舞, 轉化成圖來考慮, 也就是最多能流經k次, 在加上原來互相喜歡的男孩或女孩k'個, 就變成了每個男孩或女孩最多只有k+k'次經過的流。因此, 可以建圖為:
1.n個頂點N分別與n個男孩相連, 容量為男孩喜歡的女孩個數+不喜歡的女孩個數。
2.n個女孩分別與n個頂點M相連, 容量為女孩喜歡的男孩個數+不喜歡的男孩個數。
3.n個男孩和n個女孩之間相連。
4.源S連接n個頂點N, n個頂點M連接匯T, 容量為1。
在此圖基礎上, 用剛才求幾次完全匹配的方法跑一遍就是答案。
?
#include <algorithm> #include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <queue> #include <vector> #include <functional> using namespace std; #define N 205 #define M 105 #define oo 0x6fffffff #define nil (-1) int cap[N][N], d[N], fa[N], in[M], out[M], maxflow, S, T; void Init(int n){S = 0; T = 4*n+1;for (int i = 0; i <= T; ++i){in[i] = out[i] = 0;for (int j = 0; j <= T; ++j) cap[i][j] = 0;} } bool Bfs(int n){for (int i = 0; i <= n; ++i) d[i] = oo, fa[i] = nil;queue<int> Q;d[S] = 0; Q.push(S);while ( !Q.empty() ){int u = Q.front(); Q.pop();for (int v = 0; v <= n; ++v){if ( cap[u][v] > 0 && d[v] == oo ){d[v] = d[u] + 1;if ( v == T ) return true;Q.push(v);}}}return false; } int Dfs(int u, int n){if ( u != T ){if ( d[u] != oo ){for (int v = 0; v <= n; ++v){if ( cap[u][v] > 0 && d[v] == d[u] + 1 ){fa[v] = u;int r = Dfs(v, n);if ( r != nil && r != u ) return r;}}d[u] = oo;}} else {int cf = oo, r = fa[T];for (int i = T; i != S; i = fa[i]) cf = min(cf, cap[fa[i]][i]);maxflow += cf;for (int i = T; i != S; i = fa[i]){cap[fa[i]][i] -= cf; cap[i][fa[i]] += cf;if ( !cap[fa[i]][i] ) r = fa[i];}return r;}return nil; } int Dinic(int n){maxflow = 0;while ( Bfs(n) ) Dfs(S, n);return maxflow; } void RunTest(int n, int k){Init(n);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j){char ch;scanf(" %c", &ch);if ( 'Y' == ch ) ++out[i], ++in[j+n];cap[i+n][j+2*n] = 1;}for (int i = 1; i <= n; ++i){cap[S][i] = 1; cap[i+3*n][T] = 1;cap[i][i+n] = out[i] + k;cap[i+2*n][i+3*n] = in[i+n] + k;}int ans = 0;while ( n == Dinic(4*n+1) ){ans += 1;for (int i = 1; i <= n; ++i) cap[S][i] += 1, cap[i+3*n][T] += 1;}printf("%d\n", ans); } int main() {int n,k;while( scanf("%d%d", &n, &k) != EOF ) RunTest(n,k);return 0; } View Code?
[vijos 最小監視代價]最小割
From:https://www.vijos.org/p/1524
Solution:
題目實際就是求從1到m個傳輸節點不可達需要去掉多少邊花費代價最小。直接建圖, 源點連接1, 傳輸節點連接匯點。通過最小割的邊就是去掉后的最小代價。
?
#include <algorithm> #include <stdio.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <queue> #include <vector> #include <functional> using namespace std; #define N 105 #define M 705 #define oo 0x6fffffff #define nil (-1) struct {int c,to,next;} nod[M*2]; int adj[N], d[N], fa[N], idx[N], maxflow, now, S, T; void Init(int n){now = 0; S = 0; T = n+1;for (int i = 0; i <= T; ++i) adj[i] = nil; } int NewNode(int u, int c){nod[now].to = u; nod[now].c = c; nod[now].next = nil;return now++; } void AddEdge(int u, int v, int c){int u1 = NewNode(v, c);int v1 = NewNode(u, 0);nod[u1].next = adj[u]; adj[u] = u1;nod[v1].next = adj[v]; adj[v] = v1; } bool Bfs(int n){for (int i = 0; i <= n; ++i) d[i] = oo, fa[i] = nil;queue<int> Q;d[S] = 0; Q.push(S);while ( !Q.empty() ){int u = Q.front(); Q.pop();for (int i = adj[u]; i != nil; i = nod[i].next){int v = nod[i].to;if ( nod[i].c > 0 && d[v] == oo ){d[v] = d[u] + 1;if ( v == T ) return true;Q.push(v);}}}return false; } int Dfs(int u){if ( u != T ){if ( d[u] != oo ){for (int i = adj[u]; i != nil; i = nod[i].next){int v = nod[i].to;if ( nod[i].c > 0 && d[v] == d[u] + 1 ){fa[v] = u; idx[v] = i;int r = Dfs(v);if ( r != nil && r != u ) return r;}}d[u] = oo;}} else {int cf = oo, r = fa[T];for (int i = T; i != S; i = fa[i]) cf = min(cf, nod[idx[i]].c);maxflow += cf;for (int i = T; i != S; i = fa[i]){nod[idx[i]].c -= cf; nod[idx[i]^1].c += cf;if ( !nod[idx[i]].c ) r = fa[i];}return r;}return nil; } int Dinic(int n){maxflow = 0;while ( Bfs(n) ) Dfs(S);return maxflow; } void RunTest(int n, int m){Init(n);for (int i = 0; i < m; ++i){int a, b, cc;scanf("%d%d%d", &a, &b, &cc);AddEdge(a, b, cc); AddEdge(b, a, cc);}int k;scanf("%d", &k);for (int i = 0; i < k; ++i){int a;scanf("%d", &a);AddEdge(a, T, oo);}AddEdge(S, 1, oo);printf("%d\n", Dinic(n+1)); } int main() {int n,m;while( scanf("%d%d", &n, &m) != EOF ) RunTest(n,m);return 0; } View Code?
?
?
?
?
轉載于:https://www.cnblogs.com/leezy/p/3472910.html
總結
- 上一篇： SharePoint 2013 列表启用
- 下一篇： js中setAttribute 的兼容性