网络流 – Tgotp-Blog

1497: [NOI2006]最大获利

差点连网络流都写炸了。

看到这题容易想到最大闭合子权图,考虑建图。

从源点连向i一个流量为p[i]的边,

有一个边的时候,新建一个点,由两个端点连向这个点一个无限流量的边,这个点再连向汇点一个流量为价值的边,搞定。

c++代码如下:
[crayon-5a67216a9ae8[……]

Read more

P1345 [USACO5.4]奶牛的电信Telecowmunication

对于这道题,

很容易看出是网络流,

然后怎么建图呢。

发现此题不是删边,而是删点,理所当然一个点只能删一次,如何保证呢?

把点删一次看作容量为1的边,然后把i 与i+n连起来,对于任何与i相连接的点,把i+n与之连接起来。

跑一边dinic,搞定。

c++代码如下[……]

Read more

4819 [SDOI2017]新生舞会

对于这题

我不知有句mmp当不当讲,结构体的邻接表t4个,开成数组就ac?
这就是这题的收获。

然后,对于这道题,假设答案为c,则有a1 -c*b1 +  a2 – c*b2 -……..+an – c*bn <0

所以二分答案,搞定

 

c+[……]

Read more

P3381 【模板】最小费用最大流

跑spfa,然后dfs一样的步骤,不过要注意 反向边费用取反。

c++代码如下:

 

LuoguP2057 && BZOJ 1934: [Shoi2007]Vote 善意的投票

对于编号不同的点一种向源点连边,另外一种向汇点连边。

对于连通的两点,连无向边。

跑一边最大流。

搞定。最小割模型

c++代码如下

 

P3386 【模板】二分图匹配

用了两种算法来测试,

网络流用dinic实现:

本以为网络流可以完虐匈牙利。

可惜洛谷这题太气人,边数太多,以至于一开始我re的莫名其妙。

所以得出结论,边数多的时候用匈牙利,少的时候用网络流。

匈牙利 117ms

网络流 342ms

 

以[……]

Read more

E. Soldier and Traveling

E. Soldier and Traveling
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

st[……]

Read more

bzoj 3376 文理分科

n,m写反了引起的惨剧。

网络流问题。

题目大意:给定一个m*n的矩阵,每个格子的人可以学文或者学理,学文和学理各有一个满意度,如果以某人为中心的十字内所有人都学文或者学理还会得到一个额外满意度,求最大满意度之和

令S集为学文,T集为学理

每个人学文或者学理的满意度很好连边[……]

Read more

NOI2009植物大战僵尸

最大闭合子全图。

注意判环就好了。