输出一个整数，表示参与伏击的狼的最小数量.
题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=1001
首先应该会想到网络流。。。然后就做完了
实际上这个做法并不是很优。。。
通过平面图的知识我们可以在图的最左上和最右下建出两个新节点S和T。。。
然后将每个方格看作一个节点，两个节点的公共边作为它们之间的边权。。。
然后跑最短路即可。。效率O(n*m*log(n*m))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
int n,m,N,hang;
int cnt;
struct edge{
int r,next;
LL w;
}e[6000010];
int head[2000010];
LL h[2000010];
bool c[2000010];
priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > >q;
void insert(int u,int v,LL w){
cnt++;
//cout<<cnt<<endl;
e[cnt].r=v;
e[cnt].next=head[u];
e[cnt].w=w;
head[u]=cnt;
}
void dijkstra(){
memset(h,inf,sizeof(h));
q.push(make_pair(0,0));
h[0]=0;
while(!q.empty()){
int now=q.top().second;
LL s=q.top().first;
q.pop();
//cout<<now<<" "<<s<<" "<<head[now]<<endl;
if(c[now]==1) continue;
if(now==N+1){
printf("%lld\n",h[N+1]);return;
}
c[now]=1;
for(int i=head[now];i>0;i=e[i].next){
int H=s+e[i].w;
if(H<h[e[i].r]){
h[e[i].r]=H;
q.push(make_pair(H,e[i].r));
}
}
//cout<<1<<endl;
}
}
int main(){
int l,r;
LL ans=inf,x;
cnt=0;
scanf("%d%d",&n,&m);
if(n==1||m==1){
if(n>m) swap(n,m);
for(int i=1;i<m;i++){
scanf("%lld",&x);
if(x<ans) ans=x;
}
printf("%lld\n",ans);
return 0;
}
hang=(m-1)<<1;
N=hang*(n-1);
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++){
scanf("%lld",&x);
if(i==1) insert(0,j<<1,x);
else if(i==n) insert(hang*(n-2)+j*2-1,N+1,x);
else{
l=hang*(i-2)+j*2-1;
r=hang*(i-1)+j*2;
insert(l,r,x);
insert(r,l,x);
}
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++){
scanf("%lld",&x);
if(j==1)insert(hang*(i-1)+1,N+1,x);
else if(j==m)insert(0,hang*i,x);
else{
l=hang*(i-1)+(j-1)*2;
r=l+1;
insert(l,r,x);
insert(r,l,x);
}
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++){
scanf("%lld",&x);
l=hang*(i-1)+j*2;
r=l-1;
insert(l,r,x);
insert(r,l,x);
}
//for(int i=0;i<=N+1;i++) cout<<head[i]<<endl;
dijkstra();
return 0;
}
This passage is made by Iscream-2001.
原文：https://www.cnblogs.com/Yuigahama/p/9648154.html