Description
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：
左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下 三种类型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1) 道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的. 左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角(1,1)的窝里，现在它们要跑到右下解(N,M)的窝中去，狼王开始伏击这些兔子.当然 为了保险起见，如果一条道路上最多通过的兔子数为K，狼王需要安排同样数量的K只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔 子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.
这个题，开始目测是最大流。但是点有1000*1000个，直接套模版肯定过不去，想了好久优化的方法。。。时间过不去。后来████。于是就get到了新技能（ 怎么get的不重要对不对）
将图中的空白部分转化为一个个点点与点之间的边权值等于公共边的边权。这样从右上的点到左下的点中每一条路径都是原图的一个割。所以就转化为了一个求最短路的问题。
这种方法要求图形是已知的规则图形，一般的题目没法用（不然DINIC不就废了╮(╯_╰)╭）
/**************************************************************
Problem: 1001
User: 1115825064
Language: C++
Result: Accepted
Time:2980 ms
Memory:109680 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000100,MOD=3000003;
int n,m,f[3*N];
struct D{
int to,next,w;
}e[6*N];
int head1[3*N],tot=1;
int S,T;
void jia(int v,int u,int a)
{
tot++;e[tot].to=u;e[tot].w=a;e[tot].next=head1[v];head1[v]=tot;
}
#define LINK(x) for(int i=head1[x];i;i=e[i].next)
int que[N*3],head=0,tail=1;
bool dian[3*N];
int main()
{
// freopen("1.txt","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
T=0,S=2*n*m+1;
for(int i=0;i<n;++i)
for(int j=1;j<m;++j)
{
int a;
scanf("%d",&a);
int u=i*2*m+j,v=u-m;
if(v<0) v=T;
if(i==n-1) u=S;
jia(u,v,a);
jia(v,u,a);
}
for(int i=0;i<n-1;++i)
for(int j=0;j<m;++j)
{
int a;
scanf("%d",&a);
int u=i*2*m+j,v=u+m+1;
if(j==0)u=S;
if(j==m-1) v=T;
jia(u,v,a);
jia(v,u,a);
}
for(int i=1;i<n;++i)
for(int j=1;j<m;++j)
{
int a;
scanf("%d",&a);
int u=(i-1)*2*m+j,v=u+m;
jia(u,v,a);
jia(v,u,a);
}
que[1]=0;
dian[0]=1;
// for(int i=1;i<3*N;++i) f[i]=100000000;
memset(f,0x7f,sizeof(f));
f[0]=0;
while(head!=tail)
{
head%=MOD;
head++;
int x=que[head];
dian[x]=0;
LINK(x) if(f[x]+e[i].w<f[e[i].to])
{
f[e[i].to]=f[x]+e[i].w;
if(dian[e[i].to]==0)
{
dian[e[i].to]=1;
tail%=MOD;
que[++tail]=e[i].to;
}
}
}
printf("%d",f[S]);
}
这个文档挺不错的，挂个链接
2025年2月23日 23:29
I wouldn’t normally be so intrigued by content on this topic but the way you wrote this really grabbed my attention. It is very well thought out and interesting informative content. Thank you for sharing! 作业代写
2025年3月24日 22:22
we use wall arts at home because it is a very good and stylish decoration to add at your home“ Custom Awards
2025年3月25日 18:04
I was reading through some of your blog posts on this site and I think this web site is really instructive! Keep on putting up. 온라인바카라
2025年4月03日 19:50
Hello I want to to talk about a remark right here concerning you to definitely be able to let you know just how much i actually Liked this particular read. I have to run off in order to aTurkey Day time Supper however wanted to leave ya a simple remark. We saved a person So will end up being coming back subsequent work to see much more of yer quality posts. Keep up the standard work. TB2X Portaal
2025年4月06日 19:05
I in the past left a comment on the web site and selected alert me about latest responses. Perhaps there is a way to eliminate that system? I am getting numerous mails. Udangbet
2025年4月19日 19:45
Thanks for another informative blog. Where else could I get that type of info written in such an ideal way? I have a project that I’m just now working on, and I have been on the look out for such information. Mantap168