dinic – Tgotp-Blog

1305: [CQOI2009]dance跳舞

把一个点拆成两个点处理,即喜欢与不喜欢,由喜欢的向不喜欢连容量为k的边即可满足限制条件

基于一个认识,一个入度均为t的二分图,至少有t条不同的完全匹配,那么以此见边,具体细节见代码。

c++代码如下:

 

1497: [NOI2006]最大获利

差点连网络流都写炸了。

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

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

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

c++代码如下:
[crayon-5befe44ef2fd[......]

Read more

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