图论|BZOJ 1001: 狼抓兔子最短路|BZOJ|网络流

1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec Memory Limit: 162 MB
[ Submit][ Status] 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只狼，才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦.
Input 第一行为N,M.表示网格的大小，N,M均小于等于1000.接下来分三部分第一部分共N行，每行M-1个数，表示横向道路的权值. 第二部分共N-1行，每行M个数，表示纵向道路的权值. 第三部分共N-1行，每行M-1个数，表示斜向道路的权值. 输入文件保证不超过10M
Output 【图论|BZOJ 1001: 狼抓兔子】输出一个整数，表示参与伏击的狼的最小数量.
Sample Input 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 Sample Output 14
对于此题我觉得还是比较好如果用网络流来解题此题就会TLE 所以需要把求最小割转换成平面图上的最短路至于最小割和最短路的关系就自己在网上找吧附上代码：

#include #include #include #include #define MAXN (1000+100) #define MAXM (1000+100) #define MAXMN (MAXN*MAXM*3) using namespace std; /* 将每个三角形看作节点，连双向边： S->最左边一列三角形，边权为该三角形的左边流量； S->最下边一列三角形，边权为该三角形的下边流量；最右边一列三角形->T，边权为该三角形的右边流量；最上边一列三角形->T，边权为该三角形的上边流量；三角形->左边连着的三角形，边权为公共边流量；三角形->下边连着的三角形，边权为公共边流量；三角形->右边连着的三角形，边权为公共边流量。然后SPFA求最短路 */ struct edge { int v,next,w; }e[MAXMN*2]; int head[MAXMN],cnt=0; int dis[MAXMN]; bool vis[MAXMN]; int S,T; int n,m; void init() { freopen("1001.in","r",stdin); freopen("1001_Benedict.out","w",stdout); } void adde(int u,int v,int w) { e[cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt++; e[cnt].v=u; e[cnt].w=w; e[cnt].next=head[v]; head[v]=cnt++; } void readdata() { memset(head,-1,sizeof(head)); int w; cin>>n>>m; //初始化 T=(n-1)*(m-1)*2+1; //超级汇点 //横向：建边 for(int i=1; i<=m-1; i++) { scanf("%d",&w); adde(2*i,T,w); } for(int i=2; i<=n-1; i++) for(int j=1; j<=m-1; j++) { scanf("%d",&w); adde((i-2)*(m-1)*2+2*j-1,(i-1)*(m-1)*2+2*j,w); } for(int i=1; i<=m-1; i++) { scanf("%d",&w); adde(S,(n-2)*(m-1)*2+2*i-1,w); } //竖向：建边 for(int i=1; i<=n-1; i++) { scanf("%d",&w); adde(S,(i-1)*(m-1)*2+2*1-1,w); for(int j=2; j<=m-1; j++) { scanf("%d",&w); adde((i-1)*(m-1)*2+2*j-1-1,(i-1)*(m-1)*2+2*j-1,w); } scanf("%d",&w); adde((i-1)*(m-1)*2+2*(m-1),T,w); } //斜向：建边 for(int i=1; i<=n-1; i++) for(int j=1; j<=m-1; j++) { scanf("%d",&w); adde((i-1)*(m-1)*2+2*j-1,(i-1)*(m-1)*2+2*j,w); } } int spfa() { queueq; for(int i=S; i<=T; i++) { dis[i]=0x3f3f3f3f; vis[i]=0; } dis[S]=0; vis[S]=1; q.push(S); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u]; i!=-1; i=e[i].next) { int v=e[i].v; if(dis[v]>dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[T]; }void work() { int ans=spfa(); printf("%d\n",ans); }int main() { init(); readdata(); work(); return 0; }