网络流

网络流24题
https://www.luogu.com.cn/problem/list?tag=332

P1251 餐巾计划问题

费用流（上下界费用流，或者最小费用可行流）

P2756 飞行员配对方案问题

最大匹配

P2762 太空飞行计划问题

最大权闭合子图

P2763 试题库问题

二分图匹配求方案

P2765 魔术球问题

特殊的最小路径覆盖（为什么贪心是对的？）
注意到每个柱子上升序，每个数字前面能接的数字唯一

P2766 最长不下降子序列问题

P2770 航空路线问题

P2774 方格取数问题

全部-最小割，割掉的不选

P2775 机器人路径规划问题

机器人路径规划问题(TMP1R)题解
https://wenku.baidu.com/view/ec2c5a7616fc700abb68fc8f.html

P3254 圆桌问题

完美匹配问题，也可以贪心

P3358 最长k可重区间集问题

费用路。
// 假设 k 个人同时出发，每条路至多1个人经过，问最多走多少路。

P4014 分配问题
KM 模板题

P4015 运输问题f
费用流模板题

P4016 负载平衡问题
纸牌均分问题

P2050 [NOI2012] 美食节
经典费用流，倒数第i个，代价*i

P2053 [SCOI2007]修车
经典费用流，倒数第i个，代价*i

P2472 [SCOI2007]蜥蜴

限制在点上的最大流

P4542 [ZJOI2011]营救皮卡丘
Floyd+费用流

P4553 80人环游世界
费用流

codechef SPCLN
https://www.codechef.com/problems/SPCLN
https://www.codechef.com/problems/RIN
转化为最小割

P4217 [CTSC2010]产品销售

二分图匹配匈牙利算法
二分图带权匹配 KM算法
最大流 dinic算法
最小费用最大流 spfa暴力增广
https://www.luogu.com.cn/training/12097

一般图也可以求最大匹配带花树
很少有题目需要用到这个算法

带权匹配
有KM算法，一般没人用。

P1894 [USACO4.2]完美的牛栏The Perfect Stall

https://www.luogu.com.cn/problem/P1894
直接二分图最大匹配

P4298 [CTSC2008]祭祀

二分图，最长反链
第一问：最长反链长度
第二问：最长反链方案
第三问：哪些点可以在最长反链中

P5030 长脖子鹿放置

二分图，最大点独立集

P3355 骑士共存问题

P4304 [TJOI2013]攻击装置

二分图，最大点独立集

P3882 [JLOI2008]将军

二分图，最大匹配

P2756 飞行员配对方案问题

二分图，最大匹配，输出方案

P3033 [USACO11NOV]Cow Steeplechase G

二分图，最大点独立集

https://www.luogu.com.cn/training/12097
网络流

二分图匹配是一种特殊的网络流

https://oi-wiki.org/graph/flow/
有向
每条边有一个限制

求一个流
满足

每条边的限制必须满足
斜对称性
除了源点和汇点，每个点流量平衡

最大流：直接求
最小割：最大流最小割定理，转化为最大流直接求

特殊情况：平面图最小割，可能可以转化为最短路。

dinic 算法
好写好记
2个函数

bfs 广搜
广搜给每个点一个标号
只考虑有流量的边，从原点到每个点需要经过几个点
计算是否存在从源点到汇点有流量的路径
给每个点一个标号，在dfs中使用

dfs 深搜
经过的点，每次标号必须+1
2个参数

dfs(到了点x, 到点x有多少流量)
// 返回值，有多少流量流向了终点
// 有的人的写法是还剩下多少流量

P1345 [USACO5.4]奶牛的电信Telecowmunication
注意是删点
建图
点 i 拆成网络流中的2个点 i, i + n
原图x, y有边
网络流中
x -> y + n 容量1
y -> x + n 容量1

对于每个点i
i + n -> i 容量1

i+n 只有入边
i 只有出边
如果割掉了 i + n 到 i 的边，那么相当于这台电脑坏了
最终求 c1 到 c2 + n 的最大流

P2740 [USACO4.2]草地排水Drainage Ditches

注意是单向边

P2936 [USACO09JAN]Total Flow S

最大流

P1344 [USACO4.4]追查坏牛奶Pollutant Control

最小割，最小化最小割的边数

每条边边权 += 0.000001

或者 + 1/(m+1)
保证所有小数部分的和 < 1

求最小割
整数部分为最小割
小数部分为边数

P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

最小割
如果有的人选0和选1都不算冲突呢？
在保证最小冲突数的基础之上，最小化1的个数，最大化1的个数

P4001 [ICPC-Beijing 2006]狼抓兔子

平面图最小割转最短路

P3163 [CQOI2014]危桥

(sa, sb) -> (ta, tb) 求最大流
(sa, tb) -> (ta, sb) 求最大流
注意s -> sa 流量 na
注意s -> sb 流量 na

2对起点和终点的情况
如果是多对的？
是不是也可以通过交换起点终点来解决

P3931 SAC E#1 - 一道难题 Tree

树形DP

P1361 小M的作物

边数巨大
全部收益 - 最小割(放弃的收益)

P4313 文理分科

和小M的作物类似
这类题目可能需要ST或者线段树等数据结构优化

hdu 4621
http://acm.hdu.edu.cn/showproblem.php?pid=4621
用二维ST优化建网络流
4个边长为2的次幂的矩形，可以凑出任意矩形
有时用线段树，树链剖分来优化构图

SP4063 MPIGS - Sell Pigs
卖猪
可以请前面有共同猪圈的人代购

P2857 [USACO06FEB]Steady Cow Assignment G

二分图，双指针法

for (int i = 1, j = 1; i <= b; i++)
{
while (只用[i, j)里的牛棚没有完美匹配)
{
j++;
}
ans = min(ans, j - i);
}
printf("%d\n");

SP1693 COCONUTS - Coconuts
源点向权值为1的点连双向边，容量是1
权值为0的点向汇点连双向边，容量是1
有边的点之间连双向边，容量是1

从源点出发的边，到汇点的边，是否是双向边无所谓

SP839 OPTM - Optimal Mark
按位做，最小割，最小化最小割一边的点数

一位一位做
源点向权值为1的点连双向边，容量是 inf
权值为0的点向汇点连双向边，容量是 inf
未知权值的不连边
有边的点之间连双向边，容量是1

求出最大流最小割之后，从源点DFS，只走有剩余流量的边，能到的点就是权值一定为1的点。
如果交换源点和汇点，DFS实现起来比较麻烦

从源点出发的边，到汇点的边，是否是双向边无所谓

P2598 [ZJOI2009]狼和羊的故事

https://www.luogu.com.cn/problem/P2598

题目描述

“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。

输入格式

文件的第一行包含两个整数n和m。接下来n行每行m个整数，1表示该格子属于狼的领地，2表示属于羊的领地，0表示该格子不是任何一只动物的领地。

输出格式

文件中仅包含一个整数ans，代表篱笆的最短长度。

样例 #1

样例输入 #1

2 2
2 2 
1 1

样例输出 #1

提示

数据范围

10%的数据 n，m≤3

30%的数据 n，m≤20

100%的数据 n，m≤100

参考代码

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std;
int n,m,s,t;
int a[200020][3];
int h[10020],tot;
int v[10020];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void add(int x,int y,int z)
{
	tot++;
	a[tot][0]=h[x];
	a[tot][1]=y;
	a[tot][2]=z;
	h[x]=tot;

	tot++;
	a[tot][0]=h[y];
	a[tot][1]=x;
	a[tot][2]=0;
	h[y]=tot;
}
int bfs()
{
	int p,i;
	queue<int>q;
	memset(v,0,sizeof(v));
	v[s]=1;
	q.push(s);
	while(q.size())
	{
		p=q.front();
		q.pop();
		for(i=h[p];i;i=a[i][0])
			if(a[i][2]&&!v[a[i][1]])
			{
				v[a[i][1]]=v[p]+1;
				if(a[i][1]==t)
					return 1;
				q.push(a[i][1]);
			}
	}
	return 0;
}
int dinic(int x,int y)
{
	int i,u=y,k,p;
	if(x==t)
		return y;
	for(i=h[x];i;i=a[i][0])
	{
		if(u&&a[i][2]&&v[a[i][1]]==v[x]+1)
		{
			k=dinic(a[i][1],min(a[i][2],u));
			if(!k)
				v[a[i][1]]=0;
			u-=k;
			a[i][2]-=k;
			a[i^1][2]+=k;
		}
	}
	return y-u;
}
int main()
{
	int i,j,k,ans=0,dd;
	tot=1;
	scanf("%d %d",&n,&m);
	s=n*m;
	t=s+1;
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			for(k=0;k<4;k++)
				if(i+dx[k]>=0&&i+dx[k]<n&&j+dy[k]>=0&&j+dy[k]<m)
					add(i*m+j,(i+dx[k])*m+j+dy[k],1);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			scanf("%d",&k);
			if(k==1)
				add(s,i*m+j,0xffff);
			else if(k==2)
				add(i*m+j,t,0xffff);
		}
	while(bfs())
		while(dd=dinic(s,0x3f3f3f3f))
			ans+=dd;
	printf("%d",ans);
	return 0;
}

题解

最小割

P3866 [TJOI2009]战争游戏

最小割

P3872 [TJOI2010]电影迷

有向图最小割

P2763 试题库问题

二分图多重匹配，输出方案
https://www.luogu.com.cn/blog/ajsoabk/p2763-shi-ti-ku-wen-ti

费用流
暴力增广

P4177 [CEOI2008]order
dfs 中，枚举所有边时，是否应该跳过已经无效的边（？）
如果当前剩余流量是0，是否应该直接break。

为什么有的时候加了优化还会超时？

最大权闭合图

P3254 圆桌问题

https://www.luogu.com.cn/blog/wo-yao-AC/solution-p3254
https://60410.blog.luogu.org/solution-p3254
https://www.luogu.com.cn/blog/leozhang/solution-p3254
https://www.luogu.com.cn/blog/jxp12345678/p3254-yuan-zhuo-wen-ti
https://www.luogu.com.cn/blog/MelodyJiYang/solution-p3254

4 5 3 5
5 5 4 3

6 9
4 4 4 4 4 4
6 6 6 1 1 1 1 1 1

每个代表团去这些桌子
1 2 3 4
1 2 3 5
1 2 3 6
1 2 3 7
1 2 3 8
1 2 3 9

9 6 5 1
8 7 4 2
互相不绝对比对方好

唯一正确的方法，代表团按大到小排序
每次去最大的若干个桌子

CF387D George and Interesting Graph
枚举中心

假设删去所有的边 m
加入需要的边
中心的自环 1
中心的出度 (n-1)
中心的入度 (n-1)
除中心之外其他点之间的边 (n-1)

答案初始化为 m+3*n-2
每利用现有的一条边，答案-=2

除中心之外其他点之间的边：用最大匹配来做