BZOJ-1001 狼抓兔子 (最小割-最大流)平面图转对偶图+SPFA

时间:2021-03-27 00:59:16

1001: [BeiJing2006]狼抓兔子

Time Limit: 15 Sec Memory Limit: 162 MB

Submit: 14686 Solved: 3513

[Submit][Status][Discuss]

Description

现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:BZOJ-1001  狼抓兔子  (最小割-最大流)平面图转对偶图+SPFA

左上角点为(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

输出一个整数,表示参与伏击的狼的最小数量.

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

HINT

2015.4.16新加数据一组,可能会卡掉从前可以过的程序。

—————————————————华华丽丽的分割线————————————————-

这道题一看就是最小割问题,而由最小割-最大流定理我们可以知道,平面图最小割=平面图最大流=对偶图的最短路

然而我网络流并不是很会,正好这道题最大流会爆,故只能转对偶图跑最短路

先说一下转对偶图的转法:

这里用题目做解释:

BZOJ-1001  狼抓兔子  (最小割-最大流)平面图转对偶图+SPFA

将每个三角形看做一个节点,并分别编号1,2….,并设置两个节点,起点S和终点T,将每一条边割开,即连接各个点(三角形),新的边权等于被割掉的边的边权,然后跑SPFA即可

分析得:

对于横行:

1.第一行割开后的点(三角形)都与终点T连边

2.除去第一行和最后一行的其余割开后的两个相邻的点(三角形)连边

3.最后一行的隔开后的点(三角形)都与起点S连边

对于纵行:

1.最左边的纵行割开后与起点S连边

2.除最左最右边的纵行割开后的两个相邻点(三角形)连边

3.最右边的纵行割开后与终点T连边

对于斜行:

1.割开后与相邻两点(三角形)连边

(如上述图所示)

最后跑S到T的最短路即可

—————————————————华华丽丽的分割线————————————————-

代码如下(关于图的转换,各个公式推一下就好,其实不是很麻烦):

/**************************************************************
Problem: 1001
User: DaD3zZ
Language: C++
Result: Accepted
Time:3428 ms
Memory:124324 kb
****************************************************************/ #include<queue>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
bool visit[6000100]={false};
int cnt=0,next[6000100]={0},point[6000100]={0},v[6000100]={0},cost[6000100]={0};
int n,m,s,t;
int dis[6000100];
queue <int>que; void add(int a,int b,int c)
{
next[++cnt]=point[a];
point[a]=cnt;
v[cnt]=b;
cost[cnt]=c;
} int spfa()
{
memset(dis,127,sizeof(dis));
int now,loc;
dis[s]=0;
que.push(s);
visit[s]=true;
while (!que.empty())
{
now=que.front();que.pop();
visit[now]=false;loc=point[now];
while (loc>0)
{
if (dis[v[loc]]>dis[now]+cost[loc])
{
dis[v[loc]]=dis[now]+cost[loc];
if (visit[v[loc]]==false)
{
visit[v[loc]]=true; que.push(v[loc]);
}
}
loc=next[loc];
}
}
return dis[t];
}//裸SPFA int main()
{
scanf("%d%d",&n,&m);
s=0; t=(n-1)*(m-1)*2+1;
for (int i=1; i<=m-1; i++)
{
int x;scanf("%d",&x);
add(i*2,t,x);add(t,i*2,x);
}
for (int i=2; i<=n-1; i++)
for (int j=1; j<=m-1; j++)
{
int x;scanf("%d",&x);
add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2-m*2+1,x);
add((i-1)*(m-1)*2+j*2-m*2+1,(i-1)*(m-1)*2+j*2,x);
}
for (int i=1; i<=m-1; i++)
{
int x;scanf("%d",&x);
add((n-2)*2*(m-1)+i*2-1,s,x);
add(s,(n-2)*2*(m-1)+i*2-1,x);
}
//横行的转换
for (int i=1; i<=n-1; i++)
{
int x; scanf("%d",&x);
add((i-1)*(m-1)*2+1,s,x);
add(s,(i-1)*(m-1)*2+1,x);
for (int j=1; j<=m-2; j++)
{
scanf("%d",&x);
add((i-1)*(m-1)*2+j*2+1,(i-1)*(m-1)*2+j*2,x);
add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2+1,x);
}
scanf("%d",&x);
add((i-1)*(m-1)*2+(m-2)*2+2,t,x);
add(t,(i-1)*(m-1)*2+(m-2)*2+2,x);
}
//竖行的转换
for (int i=1; i<=n-1; i++)
for (int j=1; j<=m-1; j++)
{
int x;scanf("%d",&x);
add((i-1)*(m-1)*2+j*2-1,(i-1)*(m-1)*2+j*2,x);
add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2-1,x);
}
//斜行的转换
int ans=spfa();
printf("%d",ans);
return 0;
}

BZOJ-1001 狼抓兔子 (最小割-最大流)平面图转对偶图+SPFA的更多相关文章

  1. BZOJ 1001 狼抓兔子 &lpar;最小割转化成最短路&rpar;

    1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec  Memory Limit: 162 MBSubmit: 27715  Solved: 7134[Submit][ ...

  2. BZOJ1001&colon; &lbrack;BeiJing2006&rsqb;狼抓兔子 &lbrack;最小割 &vert; 对偶图&plus;spfa&rsqb;

    1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec  Memory Limit: 162 MBSubmit: 19528  Solved: 4818[Submit][ ...

  3. bzoj1001&colon; &lbrack;BeiJing2006&rsqb;狼抓兔子 -- 最小割

    1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec  Memory Limit: 162 MB Description 现在小朋友们最喜欢的"喜羊羊与灰太狼 ...

  4. &lbrack;bzoj1001&rsqb;狼抓兔子 最小割

    题意概述:给出一张无向图,每条边有一个权值,割掉这条边代价为它的权值,求使起点不能到达终点的最小代价. 显然能看出这是个最小割嘛,然后最小割=最大流,建图的时候特殊处理一下再跑个最大流就好了. #in ...

  5. BZOJ 1001&colon; &lbrack;BeiJing2006&rsqb;狼抓兔子 最小割

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1001 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓 ...

  6. &lbrack;bzoj 1001&rsqb;&lbrack;Beijing2006&rsqb;狼抓兔子 &lpar;最小割&plus;对偶图&plus;最短路&rpar;

    Description 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的, 而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一 ...

  7. BZOJ 1001 狼抓兔子 (网络流最小割&sol;平面图的对偶图的最短路)

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1001 算法讨论: 1.可以用最大流做,最大流等于最小割. 2.可以把这个图转化其对偶图,然 ...

  8. BZOJ 1001 狼抓兔子 平面图的最小割

    题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1001 题目大意: 见链接 思路: 求最小割,平面图的最小割等价于对偶图的最短路 直接建 ...

  9. bzoj 1001 狼抓兔子 —— 平面图最小割&lpar;最短路&rpar;

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1001 平面图最小割可以转化成最短路问题: 建图时看清楚题目的 input ... 代码如下: ...

  10. BZOJ 1001 - 狼抓兔子 - &lbrack;Dinic最大流&rsqb;&lbrack;对偶图最短路&rsqb;

    题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1001 Description现在小朋友们最喜欢的"喜羊羊与灰太狼", ...

随机推荐

  1. java类中serialversionuid 作用 是什么&quest;举个例子说明

    serialVersionUID适用于Java的序列化机制.简单来说,Java的序列化机制是通过判断类的serialVersionUID来验证版本一致性的.在进行反序列化时,JVM会把传来的字节流中的 ...

  2. UIView的layoutSubviews和drawRect方法

    UIView的layoutSubviews和drawRect方法   首先两个方法都是异步执行.layoutSubviews方便数据计算,drawRect方便视图重绘.   layoutSubview ...

  3. IOS UITableView NSIndexPath属性讲解

    IOS UITableView NSIndexPath属性讲解   查看UITableView的帮助文档我们会注意到UITableView有两个Delegate分别为:dataSource和deleg ...

  4. jquery中ajax的用法

    Jquery中队Ajax操作进行了封装,可分为3层:1.最底层$.ajax(),2.第二层load().$.get().$.post()方法,3.第三层$.getScript()和$.getJSON( ...

  5. 二叉树的递归遍历 The Falling Leaves UVa 699

    题意:对于每一棵树,每一个结点都有它的水平位置,左子结点在根节点的水平位置-1,右子节点在根节点的位置+1,从左至右输出每个水平位置的节点之和 解题思路:由于上题所示的遍历方式如同二叉树的前序遍历,与 ...

  6. 【BZOJ1146】网络管理(主席树,树状数组)

    [BZOJ1146]网络管理(主席树,树状数组) 题面 BZOJ权限题,洛谷题面 题解 树上带修改主席树 貌似和\(Count\ On\ A\ Tree\)那题很相似呀 只需要套上一个树状数组来维护修 ...

  7. Android 1&period;7 中不支持 lambda 表达式

    Error:(129, 32) 错误: -source 1.7 中不支持 lambda 表达式 (请使用 -source 8 或更高版本以启用 lambda 表达式) lambda expressio ...

  8. &lbrack;转载&rsqb;如何在ubuntu上使用github

    来源:https://blog.csdn.net/tina_ttl/article/details/51326684 https://blog.csdn.net/u013551462/article/ ...

  9. Python链接Oracle数据库

    说明:以下所需安装的所有软件版本必须跟系统一致,即系统是64位,软件就得是64位,否则会出现各种链接报错的情况. 现以64位系统,python 3.6.5  64位为例: (一)安装cx_Oracle ...

  10. 编译模块的Makefile解析

    Makefile # if not defined KERNELRELEASE, command is running from command line,need invoke kbuild sys ...