最大流

1.HDU1532  给网络图,求1->n的最大流.注意边数*2

2.HDU3572  经典建图模型,有些东西能转换为容量考虑 -> 网络流算法.  Dinic学了一个多路增广优化,能少一次递归的时间

3.HDU3277 有n个女孩和n个男孩，已知一些女孩和一些喜欢的男孩可以组成CP，并已知女孩们之间有朋友关系，如果是朋友关系可以共享一个男孩。而且每个女孩可以选择至多k个不喜欢的男孩。问最多可以进行几轮选择，保证CP组合出现过后不能再出现。 TLE （以后再补吧），。

  • 关于建图：二分答案mid轮
  • (s,i,mid) 代表每个女孩选择mid次 i∈[1,n]
  • (i,j,k) 代表每个女孩i，有另外点j，流k流量
  • (i,k,1)代表每个女孩i,可以和男孩k搭配，而且流量为1，即选择1次
  • (j,k,1)代表每个女孩i，可以和不喜欢的男孩k搭配，流量1同上
  • (k,t,mid)代表每个男孩若被mid个女孩选择后，才流向T

费用流

1.HDU1533

  • 保证最大流：能保证每个人对应一个房子
  • 保证最小费用流：MCMF

建图方式，假设有cntm个人，cnth个房子，分别对应编号[1,cntm],[cntm+1,cnth]

(s,each_m,1,0)

(each_m,each_h,1,cost(Manhattan))

(each_h,t,1,0)

2.HDU3667

  • 拆边建图
  • 费用流

3.HDU2686

一个n*n(n<=30)的矩阵,求从(1,1)出发到(n,n)的两条路径,满足除了起点和终点之外,两条路径不得有重复.求最大和

  • MAXN开小了一直TLE
  • 对于每一个点,可以接一条边到下方和右方
  • 然而对于一个点,只能选择2次.则有流经该点的流<=1
  • 但是原图不能直接构造
  • 于是对每一个节点我们开影子节点(拆点),容量为1,这样就可以限流(限制次数了)
  • 注意一下最大流的时候代价取反,对答案再取绝对值即可

4.HDU3395 最大流最大费用流

  • (0,i,1,0) i∈[1,n]每个点可以选择1条边走
  • (i,j+n,1,-(v[i]^v[j])) if(mp[i][j]==1)，连影子节点限流，因为每条鱼只能被攻击一次
  • (i,sink,1,0) 每条鱼可以不攻击其他鱼，因为可能把攻击的机会让给别人反而获益更多
  • (j,sink,1,0)