首页 > 代码库 > bzoj网络流
bzoj网络流
近期看了一些bzoj的网络流，深感智商不够。不过对于网络流又有了进一步的理解。
还是mark一下吧。
献上几篇论文：1）《最小割模型在信息学竞赛中的应用》
2）《浅析一类最小割问题》
1、bzoj1066（最大流）
题意：戳这里
思路：很明显拆点最大流模型，然后对于每个点每个高度流量限为1，那么根据最大流即为可以出去的蜥蜴的数量。
2、bzoj1077（费用流）
戳这里
3.bzoj1391（最小割）
题意：戳这里
思路：有点像最大权闭合图。。可以利用最小割的性质建图：
<S,任务,收益>
<机器，T，购买费用>，<任务，机器，租用费用>
这样，如果与T相连的边为割，表示购买机器花费更小。
如果与S相连的边为割，表示任务花费太大，不做任务更优（收益为0）。
如果<任务，机器>边为割，表示任务花费太大，不做任务更优（收益为0）。
最后总收益-最大流即为答案
4、bzoj1412（最小割）
题意：有一些格子里是狼，一些里是羊，一些是空的，要使狼和羊的格子不相通，至少要堵多少条边界。
思路：很明显的最小割
5、bzoj1433(二分图匹配)
题意：戳这里
思路：需要床位的为一边，提供床位的为一边，认识连一条边（包括自己跟自己），然后就是一个二分图最大匹配。
6、bzoj1475（最大点独立集）
题意：戳这里
思路：Amber论文里讲到的题目，很明显可以看出是个二分图模型。。
但是不容易看出是求最大点权独立集。那么构图就很显然了。
7、bzoj1497（最大密度子图）
题意：戳这里
思路：可以转化成最小割。具体看Amber论文。
8、bzoj1520(费用流)
题意：戳这里
思路：很明显的最小费用流
9、bzoj1532（最大流+二分）
题意：戳这里
思路：二分最大分数score，那么
<S,人，score>，<人,比赛,1>，<比赛,T,1>
判断流量flow = m
10、bzoj1565(tarjan+最大权闭合图)
题意：戳这里
思路：首先先把保护关系建立有向边，那么如果出现环的话，环里面的所有点，包括他能保护得点都不能取。。
那么剩下的图再进行最大权闭合图的构图
code：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define M0(a) memset(a, 0, sizeof(a)) 4 #define Inf 0x3fffffff 5 const int maxn = 1000; 6 const int maxm = 800010; 7 struct oo{ 8 int y, f, next; 9 }; 10 struct MaxFlow{ 11 int n, S, T, tot; 12 int son[maxn], dist[maxn], gap[maxn]; 13 oo e[maxm]; 14 int sap(int x, int aug){ 15 if (x == T) return aug; 16 int mind = n; 17 int sum = 0, f; 18 for (int p = son[x]; p != -1; p = e[p].next){ 19 int y = e[p].y; 20 if (dist[y] + 1 == dist[x] && e[p].f){ 21 f = sap(y, min(e[p].f, aug - sum)); 22 e[p].f -= f; 23 e[p^1].f += f; 24 sum += f; 25 if (sum == aug || dist[S] >= n) return sum; 26 } 27 if (e[p].f) mind = min(mind, dist[y]); 28 } 29 if (!sum){ 30 if (!(--gap[dist[x]])) dist[S] = n; 31 ++gap[dist[x] = mind + 1]; 32 } 33 return sum; 34 } 35 void add(int x, int y, int f){ 36 e[tot].y = y; e[tot].f = f; 37 e[tot].next = son[x]; son[x] = tot++; 38 e[tot].y = x; e[tot].f = 0; 39 e[tot].next = son[y]; son[y] = tot++; 40 } 41 42 void init(int S, int T, int n){ 43 memset(son, -1, sizeof(son)); 44 tot = 0; 45 this->S = S, this->T = T, this->n = n; 46 } 47 int maxflow(){ 48 M0(gap); 49 M0(dist); 50 gap[0] = n; 51 int ans = 0; 52 while (dist[S] < n) ans += sap(S, Inf); 53 return ans; 54 } 55 } F; 56 vector<int> e[maxn]; 57 int n, m, sum; 58 int score[31][31], use[31 * 31], vis[31 * 31]; 59 //vector<pair<int, int> > pre[35][35]; 60 void init(){ 61 for (int i = 0; i <= n * m; ++i) 62 e[i].clear(); 63 // for (int i = 0; i <= n; ++i) 64 // for () 65 int k, x, y; 66 int cur = 0; 67 for (int i = 1; i <= n; ++i) 68 for (int j = 1; j <= m; ++j){ 69 scanf("%d%d", &score[i][j], &k); 70 ++cur; 71 while (k--){ 72 scanf("%d%d", &x, &y); 73 e[cur].push_back(x*m+y+1); 74 } 75 if (j > 1) e[cur].push_back(cur-1); 76 } 77 78 } 79 /*** tarjan-begin ***/ 80 int top, Index, dfn[maxn], low[maxn], stk[maxn], col[maxn], cnt; 81 bool insta[maxn]; 82 vector<int> co[maxn]; 83 void tarjan(int u){ 84 dfn[u] = low[u] = ++Index; 85 stk[++top] = u; 86 insta[u] = true; 87 int v; 88 for (int i = 0; i < (int)e[u].size(); ++i){ 89 v = e[u][i]; 90 if (!dfn[v]){ 91 tarjan(v); 92 low[u] = min(low[v], low[u]); 93 } 94 else if (insta[v]) low[u] = min(low[u], dfn[v]); 95 } 96 if (dfn[u] == low[u]){ 97 ++cnt; 98 while (1){ 99 col[stk[top]] = cnt;100 insta[stk[top]] = false;101 if (stk[top--] == u) break; 102 } 103 }104 }105 106 void tarjan(){107 M0(dfn), M0(low), M0(insta), M0(col);108 top = cnt = Index = 0;109 for (int i = 1; i <= n*m; ++i)110 if (!dfn[i]) tarjan(i);111 for (int i = 1; i <= n * m; ++i)112 co[i].clear();113 for (int i = 1; i <= n * m; ++i)114 co[col[i]].push_back(i);115 }116 /***tarjan-end ***/117 118 void dfs(const int u){119 if (vis[u]) return;120 vis[u] = 1;121 for (int i = 0; i < (int)e[u].size(); ++i)122 dfs(e[u][i]);123 }124 125 void solve(){126 tarjan();127 M0(use);128 for (int i = 1; i <= cnt; ++i)129 if ((int)co[i].size() > 1){130 for (int j = 0; j < (int)co[i].size(); ++j)131 use[co[i][j]] = 1;132 }133 M0(vis);134 for (int i = 1; i <= n * m; ++i)135 if (use[i] && !vis[i]) dfs(i);136 int S = 0, T = n *m + 1;137 F.init(S, T, T + 1);138 int cur = sum = 0;139 for (int i = 1; i <= n; ++i)140 for (int j = 1; j <= m; ++j){141 ++cur;142 if (vis[cur]) continue; 143 if (score[i][j] >= 0) 144 F.add(S, cur, score[i][j]), sum += score[i][j];145 else146 F.add(cur, T, -score[i][j]); 147 for (int k = 0; k < (int)e[cur].size(); ++k)148 F.add(e[cur][k], cur, Inf);149 }150 int ans = sum - F.maxflow();151 printf("%d\n", ans);152 }153 154 int main(){155 // freopen("a.in", "r", stdin);156 while (scanf("%d%d", &n, &m) != EOF){157 init();158 solve(); 159 }160 }
11、bzoj1585（最小割）
题意：戳这里
思路：
拆点最小割，保证每个点流量为1
<S, 1, INF>
提到的点x : <x‘, T, INF>
对于每个点x，为1或是提到的点: <x,x‘,INF>
对于每个点x，不为1且不是提到的点:<x,x‘,1>
对于原图每条边x->y: <x‘, y, INF>和 <y‘, x, INF>
最大流即为答案。。
ps..这一题跟usaco原题改动有点大。。害我做原题时进坑了。。
12、bzoj1711（最大流）
题意：戳这里
思路：三分图匹配,记得中间那个点要拆点限流量为1
13、bzoj1741(最小点覆盖)
题意：戳这里
思路：把行列抽象出来成为一个二分图，有小行星就连一条边。那么题目就等价与求出最小的点覆盖所有的遍。
14、bzoj1779(拆点最大流)
题意：戳这里
思路：好像还不是很理解。。过后补上。
15、bzoj1797（最小割+tarjan）
题意：戳这里
思路：首先跑一边最大流。然后在残余图中进行tarjan缩点。
那么对于所有满流边：
如果连接S，T两个强联通分量，那么一定是在最小割里。
如果连接两个不同的强联通分量，可能出现在最小割里。
16、bzoj1822(二分+最大流)
题意：戳这里
思路：二分时间t，那么就可以算出在这个时间内每个巫妖可以攻击的数目。
然后建图：
<S, 巫妖， 可攻击数目>，<巫妖，可攻击到的小精灵， 1>，<小精灵， T , 1>
最后判断最大流是否为小精灵个数
比较麻烦的是判断巫妖是否攻击到小精灵，需要一点计算几何知识。
17、bzoj1834（网络流模板）
题意：戳这里
思路：<S, 1, K>, 先跑一边最大流，然后在残余网络的每条边加上一条流量Inf费用为扩容费用的边
18、bzoj1877（最小费用最大流）
题意：戳这里
思路：拆点，然后就是经典构图了
19、bzoj1927(最小费用最大流)
戳这里
20、bzoj1934（最小割）
题意：戳这里
思路：分集合很典型的最小割的应用
最初选择睡午觉 <S, i, 1>
最初选择不睡午觉 <i, T, 1>
i与j为好友， <i, j, 1> <j, i, 1>
最小割即为答案。。这应该是pty大神论文最简单的应用吧
21、bzoj1937（二分图最大权匹配问题）
题意：戳这里
思路：把所有边分为树边与非树边，那么对于费树边i，连接u，v
权值wi>=wj（所有u，v路径上的边j），所以非树边只有可能变大，树边只有可能变小
即,对于非树边i即路径上的任意树边j：
wi + di >= wj - dj
=> di + dj >= wj - wi
wj-wi为定值,那么等式几乎就跟最大权匹配的顶标的式子一样了。。
套用最大权匹配km算法。。
本来想用费用流，一想到边很多就怂了。。
22、bzoj2039（最小割）
戳这里
23、bzoj2127（最小割）
题意：戳这里
思路：可利用二元关系建图：
<S, A, w1/2>，<A, T, w2/2>
<S, B, w1/2> , <B,T,w2/2>，
<A, B, (w1+w2)/2>, <B, A, (w1 + w2)/2>
为防止出现小数，可将所有流量都流量*2，最后/2即可。
答案即为sum（喜悦值）- flow
未完待续。。。
bzoj网络流