準備開始學習最大流。模板是在網(wǎng)上抄的，感覺這個看起來比較優(yōu)雅。http://blog.csdn.net/d891320478/article/details/8424820

持續(xù)更新。

（hdu zoj poj vj 都掛了 還怎么刷題啊……）

（2016.9.6

sgu326. Perspective?

題意：一個小組有n個隊伍1~n，每場比賽一個隊伍贏，一個隊伍輸，現(xiàn)在已知每個隊伍i都已經(jīng)贏了Wi場比賽，同時知道每個隊伍還需要打Ri場比賽，包括組內(nèi)和組外，同時知道組內(nèi)還剩下的比賽場數(shù)，Aij表示i和j還需要打幾場比賽，Aij=Aji，∑(j:1~n)Aij <= Ri

問題是隊伍1能否成為小組獲勝場數(shù)最多的，可以并列第一。

>>首先讓隊伍1贏得所有的比賽，其他隊伍輸?shù)羲薪M外的比賽。然后建圖最大流。

/** 建一個源點 然后對于每一場比賽為一個點 從源點到比賽連邊，權(quán)值為比賽的總分數(shù)* 比賽這個點和比賽的兩個隊伍分別連邊 權(quán)值大于等于比賽最大分數(shù)即可* 每個隊伍到匯點連一條邊 權(quán)值應(yīng)為該隊伍和1隊分數(shù)的差值（如果分數(shù)大于1隊，應(yīng)該直接輸出no* 走一遍最大流 如果答案是所有比賽的分數(shù)和就可以滿足要求*/ #include <bits/stdc++.h>const int N = 1000; const int M = 1000000; const int INF = 1 << 30; struct Edge {int to, next, w; } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail; void addedge(int u, int v, int w) {edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; i != -1; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; j != -1; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u;u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;edge[cur[u] ^ 1].w += aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; j != -1; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }int w[N], r[N], a[N][N]; int main() {int n;while (~scanf("%d", &n)) {for (int i = 1; i <= n; ++i) scanf("%d", w+i);//每個隊伍已經(jīng)贏了多少場比賽for (int i = 1; i <= n; ++i) scanf("%d", r+i);//每個隊伍還可以打多少場比賽，包括本組和外組for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) scanf("%d", &a[i][j]);//本組剩余比賽情況w[1] += r[1]; //貪心 讓本隊全贏bool fg = false;for (int i = 2; i <= n; ++i) if (w[i] > w[1]) { fg = true; break; }if (fg) { puts("NO"); continue; }src = 1;int cnt = n+1;int sum = 0;cntE = 0;memset(head, -1, sizeof head);for (int i = 2; i <= n; ++i) for (int j = i; j <= n; ++j) {if (a[i][j] <= 0) continue;sum += a[i][j];addedge(src, cnt, a[i][j]);addedge(cnt, i, INF);addedge(cnt, j, INF);cnt++;}sink = cnt;for (int i = 2; i <= n; ++i) addedge(i, sink, w[1]-w[i]);if (sap(sink) == sum) puts("YES");else puts("NO");}return 0; } View Code

?（2016.9.7

codeforces546E-Soldier and Traveling

題意：有n個城市，m條無向圖，每個城市有ai的士兵，每個士兵可以走到相鄰的城市（只能走一步）或者原地不動。問能不能使得每個城市的士兵變成bi。

題解：首先有一個trick，就是sigma（ai）！=sigma（bi）的時候，記得輸出NO。

>>這題需要輸出點與點的轉(zhuǎn)移數(shù)量，在求最大流的過程中記錄

/* 把每個點拆成入點和出點* 從源點到每一個入點連一條 流量為該點的初始人數(shù)* 從每個點的入點到出點連一條邊 流量為該點的初始人數(shù)* 對于每條邊 從起點的入點到終點的出點連一條邊 流量為起點的初始人數(shù)* 每個出點連匯點 流量為該點的結(jié)束人數(shù)*/ #include <bits/stdc++.h>const int N = 1000; const int M = 1000000; const int INF = 1 << 30; struct Edge {int from, to, next, w; } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail;int ans[N][N];void addedge(int u, int v, int w) {edge[cntE].from = u;edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].from = v;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; i != -1; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; j != -1; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u;u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;ans[edge[cur[u]].from][edge[cur[u]].to] += aug;edge[cur[u] ^ 1].w += aug;ans[edge[cur[u] ^ 1].from][edge[cur[u] ^ 1].to] -= aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; j != -1; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }int a[N], b[N]; int main() {int n, m, p, q;while (~scanf("%d%d", &n, &m)) {cntE = 0;memset(head, -1, sizeof head);memset(ans, 0, sizeof ans);src = 2 * n + 1, sink = 2 * n + 2;int sum = 0;for (int i = 1; i <= n; ++i) {scanf("%d", a+i); sum += a[i];addedge(src, i, a[i]);addedge(i, i+n, a[i]);}int sum2 = 0;for (int i = 1; i <= n; ++i) {scanf("%d", b+i); sum2 += b[i];addedge(i+n, sink, b[i]);}for (int i = 1; i <= m; ++i) {scanf("%d%d", &p, &q);addedge(p, q+n, a[p]);addedge(q, p+n, a[q]);}if (sum != sum2) {puts("NO");continue;}if (sap(sink) != sum) {puts("NO");} else {puts("YES");for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {printf("%d%c", ans[i][j+n], j==n?'\n':' ');}}}}return 0; } View Code

codeforces653D-Delivery Bears

題意：有n個點m條有向邊，每個邊有一個容量，從這個邊走過的總重量不能超過這個容量，無重邊和自環(huán)。現(xiàn)在有x只小熊，需要所有的熊從1出發(fā)走到n點，每只熊攜帶相同質(zhì)量的貨物，問最多能運多少貨物。

>>開始還以為容量需要小數(shù)，后來發(fā)現(xiàn)想多了。。。精度什么的，1e-8wa，1e-10超時，改成循環(huán)100遍竟然就對了。。。。為什么這么神奇呢。。。。

/* 首先二分每只熊所帶的貨物重量* 對于每條路徑，用路徑容量除以每只熊的重量就是這條路所能通過熊的數(shù)量* 因為熊攜帶的重量會很小，容量又很大，所以可能爆int。。注意下。。* 要從源點到1建一個容量為x的邊* 當最大流為x的時候 說明所有熊都可以走到終點*/ #include <bits/stdc++.h> const int N = 1000; const int M = 1000000; const int INF = 1 << 30; struct Edge {int to, next, w; } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail;void addedge(int u, int v, int w) {edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; i != -1; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; j != -1; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u; u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;edge[cur[u] ^ 1].w += aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; j != -1; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }int a[N], b[N], c[N]; int main() {int n, m, x;scanf("%d%d%d", &n, &m, &x);double l = 0, r = 0;for (int i = 0; i < m; ++i) {scanf("%d%d%d", a+i, b+i, c+i);r += c[i];}src = n+1, sink = n;int cnt= 100;while (cnt--) {double mid = (l+r) / 2;memset(head, -1, sizeof head);cntE = 0;for (int i = 0; i < m; ++i) {int cap = std::min(floor(c[i]/mid), 1e8);addedge(a[i], b[i], cap);}addedge(src, 1, x);int tmp = sap(n+1);if (tmp == x) l = mid;else r = mid;}printf("%.10f\n", l*x); } View Code

?

codeforces510E-Fox And Dinner

題意：有n個狐貍1~n，每個狐貍ai歲。現(xiàn)在需要將狐貍圍桌，一個桌子的狐貍數(shù)目要大于等于3，同時相鄰的兩只狐貍年齡加起來需要是一個質(zhì)數(shù)。問分桌方式，不能分就輸出不可能。

>>開始錯的很離譜，發(fā)現(xiàn)判斷質(zhì)數(shù)寫錯了。。。后來又錯的很奇怪，發(fā)現(xiàn)sap寫錯了。。。。

感覺這題比較難，根據(jù)奇偶構(gòu)圖第一次見到，學習了。。

/* 首先容易對于兩只狐貍，如果年齡和為質(zhì)數(shù)，連邊* 因為質(zhì)數(shù)都是奇數(shù)（ai>=2）可知相鄰的狐貍年齡一定是一奇一偶* 那么一個桌子的奇數(shù)狐貍=偶數(shù)狐貍>=2* 從源點到每一個偶數(shù)建一個流量為2的邊* 每一個奇數(shù)到匯點建一個流量為2的邊* 然后年齡和為質(zhì)數(shù)的兩只狐貍之間建一條流量為1的邊* 然后跑最大流 如果流量為n就可以* 輸出比較麻煩。。看完建圖題解。。這里還想了半天Orz*/#include <bits/stdc++.h> const int N = 1000; const int M = 1000000; const int INF = 1 << 30; struct Edge {int from, to, next, w; } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail; int ans[N][N]; void addedge(int u, int v, int w) {edge[cntE].from = u;edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].from = v;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; ~i; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u; u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;edge[cur[u] ^ 1].w += aug;ans[edge[cur[u]].from][edge[cur[u]].to] += aug;ans[edge[cur[u]^1].from][edge[cur[u]^1].to] -= aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }bool isprime(int x) {int limit = sqrt(x);for (int i = 2; i <= limit; ++i) if (x % i == 0) return false;return true; }int a[N]; int vis[N]; std::vector<int> G[N]; std::vector<int> ret[N];void dfs(int x, int u) {vis[u] = 1;ret[x].push_back(u);for (unsigned i = 0; i < G[u].size(); ++i) {int v = G[u][i];if (!vis[v]) { dfs(x, v); break;}} }int main() {memset(head, -1, sizeof head);cntE = 0;int n;scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", a+i);}src = n+1, sink = n+2;int odd = 0, even = 0;;for (int i = 1; i <= n; ++i)if (a[i] & 1) addedge(i, sink, 2), ++odd;else addedge(src, i, 2), ++even;if (odd != even) {puts("Impossible");return 0;}for (int i = 1; i <= n; ++i)for (int j = i+1; j <= n; ++j)if (isprime(a[i]+a[j])){if (a[i] & 1) addedge(j, i, 1);else addedge(i, j, 1);}if (sap(sink) != n) {puts("Impossible");} else {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if (ans[i][j] == 1) G[i].push_back(j), G[j].push_back(i);}}int cnt = 0;for (int i = 1; i <= n; ++i) {if (!vis[i]) {++cnt;dfs(cnt, i);}}printf("%d\n", cnt);for (int i = 1; i <= cnt; ++i) {printf("%d", ret[i].size());for (int j = 0; j < ret[i].size(); ++j) printf(" %d", ret[i][j]);printf("\n");}}return 0; } View Code

?

（poj好了，趕緊來到poj的題壓壓驚= =）

poj2391Ombrophobic Bovines

題意：有f個農(nóng)場，每個農(nóng)場有一個雨棚，每個農(nóng)場有field[i]頭牛，每個農(nóng)場的雨棚能裝shelter[i]頭牛，然后農(nóng)場之間有p條路徑，路徑可以通過無數(shù)頭牛，但是通過路徑需要花費一些時間，問所有牛都從農(nóng)場走到雨棚的最短時間。

>>這題比較上面的感覺比較簡單了（wa了那么多次好意思說

這竟然是我poj第100題。。。

/* 源點到每個農(nóng)場連農(nóng)場本來有的數(shù)量* 雨棚到匯點連雨棚能裝的數(shù)量* 二分時間 flody求出兩點之間最短時間* 任意兩點時間小于當前二分需要時間 就把兩點的邊加入圖* 最大流等于牛的總數(shù)則符合條件 注意不能滿足輸出-1*/ #include <cstdio> #include <cstring> typedef long long ll; const int N = 500; const int M = N*N; const int INF = 1 << 30; const ll inf = 1LL<<50; struct Edge {int to, next, w; } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail;void addedge(int u, int v, int w) {edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; ~i; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u; u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;edge[cur[u] ^ 1].w += aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }ll d[N][N]; void floyd(int n) {for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (d[i][k] + d[k][j] < d[i][j])d[i][j] = d[i][k] + d[k][j]; }int field[N], shelter[N]; int main() {int f, p;while (~scanf("%d%d", &f, &p)) {int sum1 = 0, sum2 = 0;for (int i = 1; i <= f; ++i) {scanf("%d%d", &field[i], &shelter[i]);sum1 += field[i];sum2 += shelter[i];}for (int i = 1; i <= f; ++i) {for (int j = 1; j <= f; ++j) {d[i][j] = (i==j)?0:inf;}}ll l = 0, r = 0;int a, b, c;for (int i = 1; i <= p; ++i) {scanf("%d%d%d", &a, &b, &c);if (d[a][b] > c) d[b][a] = d[a][b] = c;r += c;}if (sum1 > sum2) {puts("-1");continue;}floyd(f);src = 2 * f + 1, sink = 2 * f + 2;ll ans = -1;while (l <= r) {ll mid = (l+r)>>1;memset(head, -1, sizeof head);cntE = 0;for (int i = 1; i <= f; ++i) {for (int j = 1; j <= f; ++j) {if (d[i][j]<=mid) addedge(i, j+f, INF);}}for (int i = 1; i <= f; ++i) {addedge(src, i, field[i]);addedge(i+f, sink, shelter[i]);}if (sap(sink) == sum1) {r = mid - 1;ans = mid;} else {l = mid + 1;}}printf("%lld\n", ans);}return 0; } View Code

?

(2016.9.8

hdu3605-Escape

題意：2012到了，大家要逃到別的星球去。一共有n個人，m個星球，每個人只能逃到某幾個星球，每個星球只能容納一定數(shù)量的人，問能不能全部容納。（n<10^5,m<10）

>>第一道沒看題解的題QAQ

做了好幾道題，很容易想到的建圖是把源點到每個人連邊，每個人到能去的星球連容量為1的邊，每個星球到匯點連容量為星球容量的邊，然后跑最大流看容量是否為n就可以了。

這樣的超時的。。。

然后想到把星球狀壓，因為10這個數(shù)字很容易讓人想到狀壓啊。。

想到狀壓之后一開始我是把所有狀態(tài)連匯點的，但是wa了幾次想到有點星球會重復計算，于是又把每個星球和狀態(tài)連起來。

這樣邊數(shù)是10^5 點數(shù)也是10^5 反正是從10^6優(yōu)化了一下，最大流的復雜度也不是很好算，說是O(E^2*V) ……

#include <bits/stdc++.h>using namespace std; typedef long long ll; const int N = 200005; const int M = 1000000; const int INF = 1 << 30; struct Edge {int from, to, next, w;//from一般用不到 } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail;void addedge(int u, int v, int w) {edge[cntE].from = u;edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].from = v;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; ~i; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u; u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;edge[cur[u] ^ 1].w += aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }inline int read() {char ch = getchar();int data = 0;while (ch < '0' || ch > '9') ch = getchar();do {data = data * 10 + ch-'0';ch = getchar();} while (ch >= '0' && ch <= '9');return data; } int a[N]; int main() {int n, m;while (~scanf("%d%d", &n, &m)) {memset(head, -1, sizeof head);cntE = 0;int st = (1<<m);src = n+m+st; sink = src+1;for (int i = 1; i <= n; ++i) addedge(src, i, 1);for (int i = 1; i <= n; ++i) {int tmp = 0;for (int j = 0; j < m; ++j) if (read()) tmp += (1<<j);if (tmp != 0) addedge(i, tmp+n+m, 1);}for (int i = 0; i < m; ++i) addedge(n+i+1, sink, a[i]=read());for (int i = 1; i < st; ++i)for (int j = 0; j < m; ++j)if ((1<<j)&i) addedge(i+n+m, n+j+1, a[j]);if (sap(sink) == n) puts("YES");else puts("NO");}return 0; } View Code（1045MS）

又看了下別人的題解，Orz……直接源點連狀態(tài)就好了……明明可以是10^4的。。。。不過并沒有快很多。。。

#include <bits/stdc++.h>using namespace std; typedef long long ll; const int N = 200005; const int M = 1000000; const int INF = 1 << 30; struct Edge {int to, next, w; } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail;void addedge(int u, int v, int w) {edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; ~i; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u; u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;edge[cur[u] ^ 1].w += aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }inline int read() {char ch = getchar();int data = 0;while (ch < '0' || ch > '9') ch = getchar();do {data = data * 10 + ch-'0';ch = getchar();} while (ch >= '0' && ch <= '9');return data; } int a[N]; int v[N]; int main() {int n, m;while (~scanf("%d%d", &n, &m)) {memset(head, -1, sizeof head);memset(v, 0, sizeof v);cntE = 0;int st = (1<<m);src = m+st; sink = src+1;for (int i = 1; i <= n; ++i) {int tmp = 0;for (int j = 0; j < m; ++j) if (read()) tmp += (1<<j);v[tmp]++;}for (int i = 0; i < m; ++i) addedge(i+1, sink, a[i]=read());if (v[0]) {puts("NO");continue;}for (int i = 1; i < st; ++i) {addedge(src, i+m, v[i]);for (int j = 0; j < m; ++j)if ((1<<j)&i) addedge(i+m, j+1, a[j]);}if (sap(sink) == n) puts("YES");else puts("NO");}return 0; } View Code(1029ms)

?

hdu1569-方格取數(shù)(2)

這道題。。。要哭了真是。。。

題目中文的不說了。。。把格子用(i+j)的奇偶分開就可以變成二分圖，黑白棋盤染色。。同種顏色之間不可能相交。。

然后把相鄰的黑格和白格連起來，就構(gòu)成了二分圖，然后求最大流。

二分圖的最大獨立集：在圖中選取最多的點，使任意所選兩點均不相連
最大獨立數(shù) =? 頂點數(shù) —?最大匹配數(shù)

其實我一直都不理解這個。。這里。。最大獨立點權(quán)等于點權(quán)總和-最大點權(quán)匹配。。。

然后。。。我。。。把50*50算成了250。。我從懷疑模板到懷疑人生了。。。。我花了多長時間反應(yīng)過來這個錯誤啊。。。我提交了20多次啊。。。

#include <bits/stdc++.h> const int N = 2550; const int M = 1000000; const int INF = 1 << 30; struct Edge {int to, next, w; } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail;void addedge(int u, int v, int w) {edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; ~i; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u; u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;edge[cur[u] ^ 1].w += aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }int n, m; int a[100][100]; int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; int get(int i, int j) { return i*m+j+1; } int main() {while (~scanf("%d%d", &n, &m)) {memset(head, -1, sizeof head);cntE = 0;int sum = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {scanf("%d", &a[i][j]);sum += a[i][j];}}src = n*m+1, sink = n*m+2;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if ((i+j)&1) {addedge(get(i,j), sink, a[i][j]);} else {addedge(src, get(i,j), a[i][j]);for (int k = 0; k < 4; ++k) {int ni = i + dir[k][0];int nj = j + dir[k][1];if (ni<n&&ni>=0&&nj<m&&nj>=0) {addedge(get(i,j), get(ni,nj), INF);}}}}}printf("%d\n", sum-sap(sink));}} View Code

?

（2016.9.11

POJ2699-The Maximum Number of Strong Kings

題意:有n個人，每兩個人之間都要進行一次比賽。每場比賽只有一個人勝。當一個人獲得最多的獲勝場數(shù)或者他打敗了所有獲勝場數(shù)比他多的人，他就是king，現(xiàn)在給出每個人的獲勝次數(shù)，求最多有多少個king。n<=10。

題解：很容易想到獲勝場數(shù)越多的人越容易成為king，于是我一直在想怎么貪心建圖。。。。后來還是不會。。。查題解才意識到n這么小，枚舉king的數(shù)量就可以了。。。。（暴力枚舉所有情況都可以。。。）一個trick就是獲勝局數(shù)相等的情況。。

初始化的時候出錯了。。。。點數(shù)不是n。。。。。這個要記住。。。。

讀入有坑。。。

#include <cstring> #include <vector> #include <cstdio> #include <queue>const int N = 200; const int INF = 1<<30; struct Edge { int to, cap, rev; }; std::vector<Edge> G[N]; int level[N]; int iter[N];void addedge(int u, int v, int cap) {G[u].push_back(Edge{v, cap, G[v].size()});G[v].push_back(Edge{u, 0, G[u].size()-1}); }void bfs(int s) {memset(level, -1, sizeof level);std::queue<int> que;level[s] = 0;que.push(s);while (que.size()) {int v = que.front(); que.pop();for (int i = 0; i < G[v].size(); ++i) {Edge &e = G[v][i];if (e.cap > 0 && level[e.to] < 0) {level[e.to] = level[v] + 1;que.push(e.to);}}} }int dfs(int v, int t, int f) {if (v == t) return f;for (int &i = iter[v]; i < G[v].size(); ++i) {Edge &e = G[v][i];if (e.cap > 0 && level[e.to] > level[v]) {int d = dfs(e.to, t, std::min(f, e.cap));if (d > 0) {e.cap -= d;G[e.to][e.rev].cap += d;return d;}}}return 0; }int maxflow(int s, int t) {int flow = 0;for (; ;) {bfs(s);if (level[t] < 0) return flow;memset(iter, 0, sizeof iter);int f;while ((f = dfs(s, t, INF)) > 0) flow += f;}return flow; }int a[N]; void input(int &n) {char str[100];gets(str);int val = 0, len = strlen(str);for (int i = 0; i < len; i++) {if (str[i] >= '0' && str[i] <= '9') {val = val * 10 + str[i] - '0';if (i == len-1 || str[i+1] < '0' || str[i+1] > '9')a[++n] = val, val = 0;}} }int main() {int T;scanf("%d", &T); getchar();while (T--) {int n = 0;int sum = 0;int maxn = 0;input(n);for(int i = 1; i <= n; ++i) {sum += a[i];maxn = std::max(maxn, a[i]);}//for (int i =1; i <= n; ++i) printf("%d ", a[i]); printf("%d %d\n", maxn, sum);int ans = 0; int src = 0; int sink = n*n+n+1;for (int k = 1; k <= n; ++k) {for (int i = 0; i <= sink; ++i) G[i].clear();for (int i = 1; i <= n; ++i) {for (int j = i+1; j <= n; ++j) {int tmp = i * n + j;addedge(src, tmp, 1);addedge(tmp, i, 1);if (i < k || a[i] == a[j]) addedge(tmp, j, 1);}}for (int i = 1; i <= n; ++i) addedge(i, sink, a[i]);int tmp = maxflow(src, sink);if (tmp >= sum) {ans = n-k+1;break;}}printf("%d\n", ans);}return 0; } View Code

?

POJ 3281--Dining

題意：有f種食物d中飲料和n頭牛，每個牛要吃食物和飲料，每個牛對食物和飲料都有要求，只吃某幾種。。。而一種食物和一種飲料只能被一只牛吃，現(xiàn)在求最多有多少只牛既能吃到食物又能喝到飲料。。

人不如牛啊。。。。。。

一直在想怎么分解組合食物，然而正解是分解牛。。。突然發(fā)現(xiàn)數(shù)組開大了會慢好多Orz。。。。

src--food--cow_food--cow_drink--drink--sink

#include <cstring> #include <vector> #include <cstdio> #include <queue>const int N = 1000; const int M = 1000000; const int INF = 1 << 30; struct Edge {int from, to, next, w;//from一般用不到 } edge[M]; int head[N], cntE; int src, sink; int pre[N], cur[N], dis[N], gap[N]; int que[N], open, tail;void addedge(int u, int v, int w) {edge[cntE].from = u;edge[cntE].to = v;edge[cntE].w = w;edge[cntE].next = head[u];head[u] = cntE++;edge[cntE].from = v;edge[cntE].to = u;edge[cntE].w = 0;edge[cntE].next = head[v];head[v] = cntE++; } void BFS() {int i, u, v;memset(gap, 0, sizeof(gap));memset(dis, -1, sizeof(dis));open = tail = 0;que[open] = sink;dis[sink] = 0;while (open <= tail) {u = que[open++];for (i = head[u]; ~i; i = edge[i].next) {v = edge[i].to;if (edge[i].w != 0 || dis[v] != -1) continue;que[++tail] = v;++gap[dis[v] = dis[u] + 1];}} } int sap(int n) { //編號從1開始 1~nint i, v, u, flow = 0, aug = INF;int flag;BFS();gap[0] = 1;for (i = 1; i <= n; i++) cur[i] = head[i];u = pre[src] = src;while (dis[src] < n) {flag = 0;for (int j = cur[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && dis[u] == dis[v] + 1) {flag = 1;if (edge[j].w < aug) aug = edge[j].w;pre[v] = u; u = v;if (u == sink) {flow += aug;while (u != src) {u = pre[u];edge[cur[u]].w -= aug;edge[cur[u] ^ 1].w += aug;}aug = INF;}break;}cur[u] = edge[j].next;}if (flag) continue;int mindis = n;for (int j = head[u]; ~j; j = edge[j].next) {v = edge[j].to;if (edge[j].w > 0 && mindis > dis[v]) {mindis = dis[v];cur[u] = j;}}if (--gap[dis[u]] == 0) break;++gap[dis[u] = mindis + 1];u = pre[u];}return flow; }// src--food--cow_food--cow_drink--drink--sink int main() {int n, f, d;scanf("%d%d%d", &n, &f, &d);src = 2*n+f+d+1;sink = 2*n + f + d + 2;memset(head, -1, sizeof head);cntE = 0;for (int i = 1; i <= f; ++i) addedge(src, i, 1);for (int i = 1; i <= d; ++i) addedge(f+n*2+i, sink, 1);int fi, di;int a, b;for (int k = 1; k <= n; ++k) {scanf("%d%d", &fi, &di);addedge(f+k, f+n+k, 1);for (int i = 0; i < fi; ++i) {scanf("%d", &a);addedge(a, f+k, 1);}for (int i = 0; i < di; ++i) {scanf("%d", &b);addedge(f+n+k, n*2+f+b, 1);}}printf("%d\n", sap(sink));return 0; } View Code

?

（2016.9.12

http://blog.csdn.net/hnust_xiehonghao/article/details/11050217

題意：有一條東西向流淌的河,寬為 W,河中有 N 塊石頭,每塊石頭的坐標(Xi, Yi)和最大承受人數(shù) Ci 已知。現(xiàn)在有 M 個游客在河的南岸,他們想穿越這條河流,但是每個人每次最遠只能跳 D 米,每跳一次耗時 1 秒。問他們能否全部穿越這條河流,如果能,最少需要多長時間。 <= N <= 50, 0 < M <= 50, 0 <= D <= 1000, 0 < W(0<= 1000, 0 < Xi < 1000, 0 < Yi < W, 0 <= Ci <= 1000)。剛看完這題，想當然的認為它是一道最小費用流問題。但是當WA之后我才明白，這題并不是去求一個給定網(wǎng)絡(luò)的最大流，而是計算這個網(wǎng)絡(luò)隨著時間 推移每次能夠留出多少流量。我們通過枚舉時間的方式來決定在什么時刻能夠把所有的人全部送到對岸。注意人是可以從河這岸的任意x坐標出發(fā)的。（開始人都在X軸上.對岸可以看為 Y = W的一條直線）

>>見了鬼了 CE了好多次 同樣的代碼 一會CE 一會運行 。。。。

這題應(yīng)該是我做的這些題里面最難的了=。=

這個分解的竟然是時間。。。因為n和m都非常小，又可以知道時間最多花費n+m，否則過不去，所以枚舉需要的時間就可以了。。。

每增加單位時間，就增加通往新時間的邊。。。。

因為每個點都有流量限制，所以還要拆點。。。。

一直過不了樣例。。。。照著別人的代碼一點一點改還是不對。。。。后來終于意識到每一次的流量是要相加的（別人的dinic貌似不是這樣的？。。。）。。。反正坑了好久。。

#include <cstring> #include <vector> #include <cstdio> #include <queue> using namespace std; typedef long long ll;int Scan() {int res = 0, flag = 0;char ch;if((ch = getchar()) == '-') flag = 1;else if(ch >= '0' && ch <= '9') res = ch - '0';while((ch = getchar()) >= '0' && ch <= '9')res = res * 10 + (ch - '0');return flag ? -res : res; }const int N = 10010; const int INF = 1<<30; struct Edge { int to, cap, rev; }; std::vector<Edge> G[N]; int level[N]; int iter[N];void addedge(int u, int v, int cap) {G[u].push_back((Edge){v, cap, G[v].size()});G[v].push_back((Edge){u, 0, G[u].size()-1}); }void bfs(int s) {memset(level, -1, sizeof level);std::queue<int> que;level[s] = 0;que.push(s);while (que.size()) {int v = que.front(); que.pop();for (unsigned i = 0; i < G[v].size(); ++i) {Edge &e = G[v][i];if (e.cap > 0 && level[e.to] < 0) {level[e.to] = level[v] + 1;que.push(e.to);}}} }int dfs(int v, int t, int f) {if (v == t) return f;for (int &i = iter[v]; i < (int)G[v].size(); ++i) {Edge &e = G[v][i];if (e.cap > 0 && level[e.to] > level[v]) {int d = dfs(e.to, t, std::min(f, e.cap));if (d > 0) {e.cap -= d;G[e.to][e.rev].cap += d;return d;}}}return 0; }int maxflow(int s, int t) {int flow = 0;for (; ;) {bfs(s);if (level[t] < 0) return flow;memset(iter, 0, sizeof iter);int f;while ((f = dfs(s, t, INF)) > 0) flow += f;}return flow; }int x[55], y[55], c[55]; int dis[55][55]; int n, m, d, w;int cal(int a, int b) { return (x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]); } int get1(int x, int t) { return (t-1) * n + x + 1; } int get2(int x, int t) { return 5000 + (t-1) * n + x + 1; }int main() {n = Scan(); m = Scan(); d = Scan(); w = Scan();for (int i = 1; i <= n; ++i) x[i] = Scan(), y[i] = Scan(), c[i] = Scan();if (w <= d) { puts("1"); return 0; }for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)dis[i][j] = (cal(i, j) <= d*d) ? 1 : 0;int ans = 0;int src = 0, sink = 1;for (int t = 1; t <= n+m; ++t) {for (int i = 1; i <= n; ++i) {if (y[i] <= d) addedge(src, get1(i, t), INF);if (y[i]+d >= w) addedge(get2(i,t), sink, INF);addedge(get1(i, t), get2(i, t), c[i]);for (int j = 1; j <= n; ++j)if (dis[i][j]) addedge(get2(i, t), get1(j, t+1), INF);}ans += maxflow(src, sink);if (ans >= m) {printf("%d\n", t+1);break;}}if (ans < m) puts("IMPOSSIBLE");return 0; } View Code

?

先刷到這，有時間還要做套最小割的題= =

轉(zhuǎn)載于:https://www.cnblogs.com/wenruo/p/5847034.html

總結(jié)

以上是生活随笔為你收集整理的最大流总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。