knowledge


网络流-最大流

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
inline bool bfs()
{
memset(dis, -1, sizeof(dis));
queue<int> q;
q.push(s); dis[s] = 0;
while(!q.emtry()) {
int u = q.front(); q.pop();
for (int i=h[u]; i; i=nex[i]) {
int v = to[i];
if (dis[v] == -1 && c[i] > 0) {
dis[v] = dis[u] + 1;
if (v == t) return 1;
q.push(v);
}
}
}
return 0;
}
int max_flow(int x, int MIN)
{
if (x == t || MIN == 0) return MIN:
int used = 0, w;
for (int i=h[x]; i; i=nex[i]) {
int v = to[i];
if (dis[v] == dis[u] + 1 && c[i] > 0 && (w = max_flow(v, Min(MIN, c[i])))) {
c[i] -= w; c[i^1] += w;
used += w; MIN -= w;
if (MIN == 0) break;
}
}
return used;
}

例题

洛谷1231教辅的组成

拆点 因为书只能选一次 所以将书拆成两个点连一条容量为1的边
从练习册往书的一个点连容量为1的边 从书的另一个点往答案连容量为1的边
建一个超级源和超级汇 从超级源往练习册连一条容量为1的边 从答案往超级汇连一条容量为1的边
然后跑最大流就可以了!!!

洛谷3410拍照

∑get - ∑cost = ans ----> ∑can_get - ∑not_get - ∑cost = ans
所以只需要得到∑not_get + ∑cost的最大值就可以了
我们可以从超级源向每一个需要拍照的人建一条容量为可以到的钱  然后从要带的人向超级汇建一条
容量为如果带着个人我们要付的钱  中间点的连线则按输入给的关系连且容量为INF的边就可以了
然后跑最小割就可以了!!!
解释:如果割掉和超级源相连的点则表示这些点我们不去满足就是∑now_get 如果割掉和超级汇连的
     点则表示我们需要带这些就是∑cost 得到的最小割就是max(∑not_get+∑cost)

洛谷2825游戏

对于每一行每一列我们分别进行分块 因为一个炸弹一次可以炸一列和一行 所以如果这一行无硬石头
则这一行属于一个块 如果有一个硬石头则让记块器++ 列也一样
这样我可以得到(i,j)在行上属于哪一块在列上属于哪一块 如果可以放炸弹则让行向列连一条容量为
1的边
同样从超级源向行所分成的块连容量为1的边 从列向超级汇连容量为1的边
然后跑最大流就可以了!!!