题目链接
P4001 [ICPC-Beijing 2006] 狼抓兔子
[ICPC-Beijing 2006] 狼抓兔子
题目描述
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：
左上角点为 \((1,1)\), 右下角点为 \((N,M)\) (上图中 \(N=3\), \(M=4\)).有以下三种类型的道路:
-
\((x,y)\rightleftharpoons(x+1,y)\)
-
\((x,y)\rightleftharpoons(x,y+1)\)
-
\((x,y)\rightleftharpoons(x+1,y+1)\)
道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的。左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角 \((1,1)\) 的窝里，现在它们要跑到右下角 \((N,M)\) 的窝中去，狼王开始伏击这些兔子。当然为了保险起见，如果一条道路上最多通过的兔子数为 \(K\)，狼王需要安排同样数量的 \(K\) 只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。
输入格式
第一行两个整数 \(N,M\)，表示网格的大小。
接下来分三部分。
第一部分共 \(N\) 行，每行 \(M-1\) 个数，表示横向道路的权值。
第二部分共 \(N-1\) 行，每行 \(M\) 个数，表示纵向道路的权值。
第三部分共 \(N-1\) 行，每行 \(M-1\) 个数，表示斜向道路的权值。
输出格式
输出一个整数，表示参与伏击的狼的最小数量。
样例 #1
样例输入 #1
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
样例输出 #1
14
提示
数据规模与约定
对于全部的测试点，保证 \(3 \leq N,M \leq 1000\)，所有道路的权值均为不超过 \(10^6\) 的正整数。
解题思路
最小割
这题不难发现本质上其实就是在找最小割，因为所有的点，都可以分为两个集合 \((1,1)\) 和 \((n,m)\) 属于两个不同的集合，兔子一定要从属于 \(s\) 的集合走向属于 \(t\) 的集合，即都要通过两个集合中形成的边，即对应流网络中的割边，要求最小值，即对应最小割，本题 dinic 勉强过了
- 时间复杂度：\(O(n^2m)\)
最小割平面图转最短路
但还是不够优秀，可以发现这样的图是平面图（即从平面上来看，两条边相交的只能是已经存在的顶点，即一条边跨越另外一条边不行）
有一个重要的结论：\(平面图最小割=平面图的对偶图的最短路\)
\(\color{red}{对偶图是什么？}\)
以下是一个平面图转化为对偶图的过程：
如果现在要求 \(1\) 到 \(6\) 的最小割该如何转化为对偶图的最短路问题？建立对偶图后，即以 \(1\) 和 \(3\) 之间的边为例，这时该边上的面表示的点向该边下的面表示的点连边，边权为 \(1\) 到 \(3\) 的边权，不难发现：这样的割边可以对应上最短路的某条边，以 \(1-3-5-6\) 这部分的边的下面的平面看作起点 \(s\)，\(1-2-4-5\) 这部分的边的上面的平面看作终点 \(t\)，建立完对偶图后，求从 \(s\) 到 \(t\) 的最短路即为 \(1\) 到 \(6\) 的最小割
回到本题
同理，要求解 \((1,1)\) 到 \((n,m)\) 的最小割，建立对偶图，左下部分的平面看作起点 \(s\)，右上部分的平面看作终点 \(t\)，建立对偶图时，\(s\) 要通过左下边界的边和对应的平面连边，\(t\) 要通过右上边界的边和对应的平面连边
还有一个常见的难点：\(\color{red}{如何建立对偶图？}\)
对于一个这样的图，很容易如下编号：
即对于一个点 \((i,j)\)，其作为小矩形的左上角，通过这个点即可判断区域，即：
红色区域表示的点为 \(2\times (i-1)\times (m-1)+2\times (j-1)+2\)，同理可得到另外一块区域为 \(2\times (i-1)\times (m-1)+2\times (j-1)+1\)，这样标号即可解决问题，求 \(s\) 到 \(t\) 的最短路即为答案
- 时间复杂度：\(O(nlogn)\)
代码
- dinic
// Problem: P4001 [ICPC-Beijing 2006] 狼抓兔子
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4001
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=1000005,M=N*6,inf=1e9;
int n,m,S,T;
int h[N],f[M],e[M],ne[M],idx;
int d[N],q[N],hh,tt,cur[N];
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=c,ne[idx]=h[b],h[b]=idx++;
}
int get(int x,int y)
{
return x*m+y;
}
bool bfs()
{
memset(d,-1,sizeof d);
d[S]=hh=tt=0;
q[0]=S;
cur[S]=h[S];
while(hh<=tt)
{
int x=q[hh++];
for(int i=h[x];~i;i=ne[i])
{
int y=e[i];
if(d[y]==-1&&f[i])
{
d[y]=d[x]+1;
cur[y]=h[y];
if(y==T)return true;
q[++tt]=y;
}
}
}
return false;
}
int dfs(int x,int limit)
{
if(x==T)return limit;
int flow=0;
for(int i=cur[x];~i&&flow<limit;i=ne[i])
{
cur[x]=i;
int y=e[i];
if(d[y]==d[x]+1&&f[i])
{
int t=dfs(y,min(f[i],limit-flow));
if(!t)d[y]=-1;
f[i]-=t,f[i^1]+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())while(flow=dfs(S,inf))res+=flow;
return res;
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
int x;
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
{
scanf("%d",&x);
add(get(i,j),get(i,j+1),x);
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&x);
add(get(i,j),get(i+1,j),x);
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
{
scanf("%d",&x);
add(get(i,j),get(i+1,j+1),x);
}
S=get(1,1),T=get(n,m);
printf("%d",dinic());
return 0;
}
- 平面图最短路
// Problem: P4001 [ICPC-Beijing 2006] 狼抓兔子
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4001
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=2000005,M=N*3;
int n,m;
int h[N],ne[M],e[M],w[M],idx;
int d[N],S,T;
void add(int a,int b,int c)
{
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,w[idx]=c,ne[idx]=h[b],h[b]=idx++;
}
void dijkstra()
{
memset(d,0x3f,sizeof d);
d[S]=0;
priority_queue<PII,vector<PII>,greater<PII>> q;
q.push({0,S});
while(q.size())
{
auto t=q.top();
q.pop();
int x=t.se,v=t.fi;
if(x==T)return ;
if(d[x]==v)
for(int i=h[x];~i;i=ne[i])
{
int y=e[i];
if(d[y]>d[x]+w[i])
{
d[y]=d[x]+w[i];
q.push({d[y],y});
}
}
}
}
int get(int x,int y,int t)
{
return 2*(x-1)*(m-1)+2*(y-1)+t;
}
int main()
{
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
T=2*(n-1)*(m-1)+1;
int x;
for(int i=1;i<m;i++)
{
scanf("%d",&x);
add(get(1,i,2),T,x);
}
for(int i=2;i<n;i++)
for(int j=1;j<m;j++)
{
scanf("%d",&x);
add(get(i-1,j,1),get(i,j,2),x);
}
for(int i=1;i<m;i++)
{
scanf("%d",&x);
add(S,get(n-1,i,1),x);
}
for(int i=1;i<n;i++)
{
scanf("%d",&x);
add(S,get(i,1,1),x);
for(int j=2;j<m;j++)
{
scanf("%d",&x);
add(get(i,j-1,2),get(i,j,1),x);
}
scanf("%d",&x);
add(get(i,m-1,2),T,x);
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
{
scanf("%d",&x);
add(get(i,j,1),get(i,j,2),x);
}
dijkstra();
printf("%d",d[T]);
return 0;
}