BZOJ P1001 [BeiJing2006]狼抓兔子
题目
题目描述
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：
左上角点为 \((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
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\) 的正整数。
题解
此题要求参与伏击的狼的最小数量，也就是整张图的最小割，由最小割最大流定理我们只需要求此图的最大流即可。
写了个 Dinic，但是没跑过，MLE 了，代码如下：
#include
#include
#include
#include
#define ll long long
#define pb push_back
using namespace std;
const int MAXN=1e6+5,INF=0x7fffffff;
struct Edge{
int to,nxt;
ll c,f;
};
int n,m,s,t,cnt;
array c,d,head;
array vis;
vector e;
void AddEdge(int u,int v,ll c){
e.pb({v,head[u],c,0});
head[u]=e.size()-1;
e.pb({u,head[v],0,0});
head[v]=e.size()-1;
}
bool BFS(){
vis.fill(false);
d[s]=0,vis[s]=true;
queue q;
q.push(s);
c[s]=head[s];
while(!q.empty()){
int cur=q.front();
q.pop();
for(int i=head[cur];i!=-1;i=e[i].nxt){
Edge ed=e[i];
if(!vis[ed.to] && ed.c>ed.f){
vis[ed.to]=true;
c[ed.to]=head[ed.to];
d[ed.to]=d[cur]+1;
q.push(ed.to);
}
}
}
return vis[t];
}
ll DFS(int cur,ll f){
if(cur==t || f==0) return f;
ll flow=0;
for(int& i=c[cur];i!=-1;i=e[i].nxt){
Edge& ed=e[i];
if(d[cur]+1==d[ed.to]){
ll g=DFS(ed.to,min(f,ed.c-ed.f));
if(g>0){
ed.f+=g,e[i^1].f-=g;
flow+=g,f-=g;
if(f==0) break;
}
}
}
return flow;
}
ll Dinic(){
s=1,t=n*m;
ll flow=0;
c.fill(-1);
while(BFS()) flow+=DFS(s,INF);
return flow;
}
int main(){
head.fill(-1);
cin>>n>>m;
for(int i=0;i>c;
AddEdge(i*m+j,i*m+j+1,c);
AddEdge(i*m+j+1,i*m+j,c);
}
for(int j=0;j>c;
AddEdge(i+j*m,i+(j+1)*m,c);
AddEdge(i+(j+1)*m,i+j*m,c);
}
for(int j=0;j>c;
AddEdge(i+j*m,i+(j+1)*m+1,c);
AddEdge(i+(j+1)*m+1,i+j*m,c);
}
cout< 于是只好换方法，考虑样例的图，在每一个区块里建点，然后连边，如图所示：
这样每条边都被我们转化成了另一条对应的边，观察后不难发现，此图的最小割就是左下角点到右上角点的最短路，可以用 Dijkstra 算法求得。
建点和边的时候要注意序号，不要计算错了。
Code :
#include
#include
#include
#include
#define ll long long
#define pb push_back
using namespace std;
const int MAXN=2e6+5,INF=0x7fffffff;
struct Edge{
int to,w,nxt;
};
struct cmp{
bool operator()(Edge a,Edge b){
return a.w>b.w;
}
};
int n,m;
array d,head;
array vis;
vector e;
void AddEdge(int u,int v,int w){
e.pb({v,w,head[u]});
head[u]=e.size()-1;
e.pb({u,w,head[v]});
head[v]=e.size()-1;
}
void Dijkstra(int s){
vis.fill(false);
d.fill(INF);
d[s]=0;
priority_queue,cmp> q;
q.push({s,0,-1});
while(!q.empty()){
int v=q.top().to;
q.pop();
if(vis[v]) continue;
vis[v]=true;
for(int i=head[v];i!=-1;i=e[i].nxt){
int t=e[i].to;
if(!vis[t] && d[t]>d[v]+e[i].w){
d[t]=d[v]+e[i].w;
q.push({t,d[t],-1});
}
}
}
return;
}
int main(){
head.fill(-1);
cin>>n>>m;
int w;
for(int i=1;i<=n;i++) // 横边
for(int j=1;j<=m-1;j++){
cin>>w;
if(i==1) AddEdge(j,2*(n-1)*(m-1)+1,w);
else if(i==n) AddEdge(((n-1)*2-1)*(m-1)+j,0,w);
else AddEdge((m-1)*((i-1)*2-1)+j,(m-1)*((i-1)*2-1)+j+(m-1),w);
}
for(int i=1;i<=n-1;i++) // 竖边
for(int j=1;j<=m;j++){
cin>>w;
if(j==1) AddEdge(0,(m-1)*(i*2-1)+1,w);
else if(j==m) AddEdge((i*2-1)*(m-1),2*(n-1)*(m-1)+1,w);
else AddEdge((i-1)*2*(m-1)+j-1,(i-1)*2*(m-1)+j-1+m,w);
}
for(int i=1;i<=n-1;i++) // 斜边
for(int j=1;j<=m-1;j++){
cin>>w;
AddEdge((i-1)*2*(m-1)+j,(i-1)*2*(m-1)+j+(m-1),w);
}
Dijkstra(0);
cout<