经典例子：

例1：P4001 [ICPC-Beijing 2006]狼抓兔子

本题表面上是最小割，利用最大流可以求最小割，但是裸的dinic对n*m(n,m<=1000)会炸掉，虽然优化后可以通过，但是复杂度依然玄学，本题是网格图上求最大割，可以转化为对偶图求其最短路。

对偶图就是把图中分成的块看作新图中的一个点，原图的边连着连个块，如下图：

狼抓兔子-1

红色数字的就是新图中的点，原图中的边如果连接了两个新图中两个点，就是新图中的边，这种转化就把原图转成了对偶图。

对偶图有很多性质，其中一个重要的性质就是原图的最小割-最大流，就是对偶图起点到终点的最短路，原因如下图：

狼抓兔子-2

从起点到终点的路径就是原图的一个割，那么最短路径肯定就是最小割。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
struct node{
	int to,dis,next;
}edge[N*3];
int head[N],tot;
int n,m;
int d[N],vis[N];
void add(int from,int to,int dis)
{
	edge[++tot].to=to;	edge[tot].dis=dis;
	edge[tot].next=head[from];
	head[from]=tot;
}
void dijkstra(int s)
{
	priority_queue<pair<int ,int> >que;
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	que.push(make_pair(0,s));
	d[s]=0;
	while(que.size())
	{
		int x=que.top().second;que.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to,w=edge[i].dis;
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				que.push(make_pair(-d[y],y));
			}
		}
	}
	
}
int main()
{
	scanf("%d%d",&n,&m);
	int st,ed;
	st=(n-1)*(m-1)*2+1;
	ed=st+1;
	int blok1,blok2,val;
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
		{
			if(i<n)
				blok1=(i-1)*(m-1)*2+j;
			else
				blok1=st;
			if(i>1)
				blok2=(i-2)*(m-1)*2+m-1+j;
			else
				blok2=ed;
			scanf("%d",&val);
			add(blok1,blok2,val);
			add(blok2,blok1,val);				
		}
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
		{
			if(j<m)
				blok1=(i-1)*(m-1)*2+m-1+j;
			else 
			    blok1=ed;
			if(j>1)
				blok2=(i-1)*(m-1)*2+j-1;
			else
				blok2=st;
			scanf("%d",&val);
			add(blok1,blok2,val);
			add(blok2,blok1,val);
		}
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++)
		{
			blok1=(i-1)*(m-1)*2+j;
			blok2=blok1+m-1;
			scanf("%d",&val);
			add(blok1,blok2,val);
			add(blok2,blok1,val);
		}
	dijkstra(st);
	printf("%d",d[ed]);	

	return 0;
}

学习完毕

{{ select(1) }}

• YES
• NO