1001: [BeiJing2006]狼抓兔子
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 14686 Solved: 3513
[Submit][Status][Discuss]
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
输出一个整数,表示参与伏击的狼的最小数量.
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新加数据一组,可能会卡掉从前可以过的程序。
—————————————————华华丽丽的分割线————————————————-
这道题一看就是最小割问题,而由最小割-最大流定理我们可以知道,平面图最小割=平面图最大流=对偶图的最短路
然而我网络流并不是很会,正好这道题最大流会爆,故只能转对偶图跑最短路
先说一下转对偶图的转法:
这里用题目做解释:
将每个三角形看做一个节点,并分别编号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的更多相关文章
-
BZOJ 1001 狼抓兔子 (最小割转化成最短路)
1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 27715 Solved: 7134[Submit][ ...
-
BZOJ1001: [BeiJing2006]狼抓兔子 [最小割 | 对偶图+spfa]
1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 19528 Solved: 4818[Submit][ ...
-
bzoj1001: [BeiJing2006]狼抓兔子 -- 最小割
1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec Memory Limit: 162 MB Description 现在小朋友们最喜欢的"喜羊羊与灰太狼 ...
-
[bzoj1001]狼抓兔子 最小割
题意概述:给出一张无向图,每条边有一个权值,割掉这条边代价为它的权值,求使起点不能到达终点的最小代价. 显然能看出这是个最小割嘛,然后最小割=最大流,建图的时候特殊处理一下再跑个最大流就好了. #in ...
-
BZOJ 1001: [BeiJing2006]狼抓兔子 最小割
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1001 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓 ...
-
[bzoj 1001][Beijing2006]狼抓兔子 (最小割+对偶图+最短路)
Description 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的, 而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一 ...
-
BZOJ 1001 狼抓兔子 (网络流最小割/平面图的对偶图的最短路)
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1001 算法讨论: 1.可以用最大流做,最大流等于最小割. 2.可以把这个图转化其对偶图,然 ...
-
BZOJ 1001 狼抓兔子 平面图的最小割
题目链接: https://www.lydsy.com/JudgeOnline/problem.php?id=1001 题目大意: 见链接 思路: 求最小割,平面图的最小割等价于对偶图的最短路 直接建 ...
-
bzoj 1001 狼抓兔子 —— 平面图最小割(最短路)
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1001 平面图最小割可以转化成最短路问题: 建图时看清楚题目的 input ... 代码如下: ...
-
BZOJ 1001 - 狼抓兔子 - [Dinic最大流][对偶图最短路]
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1001 Description现在小朋友们最喜欢的"喜羊羊与灰太狼", ...
随机推荐
-
java类中serialversionuid 作用 是什么?举个例子说明
serialVersionUID适用于Java的序列化机制.简单来说,Java的序列化机制是通过判断类的serialVersionUID来验证版本一致性的.在进行反序列化时,JVM会把传来的字节流中的 ...
-
UIView的layoutSubviews和drawRect方法
UIView的layoutSubviews和drawRect方法 首先两个方法都是异步执行.layoutSubviews方便数据计算,drawRect方便视图重绘. layoutSubview ...
-
IOS UITableView NSIndexPath属性讲解
IOS UITableView NSIndexPath属性讲解 查看UITableView的帮助文档我们会注意到UITableView有两个Delegate分别为:dataSource和deleg ...
-
jquery中ajax的用法
Jquery中队Ajax操作进行了封装,可分为3层:1.最底层$.ajax(),2.第二层load().$.get().$.post()方法,3.第三层$.getScript()和$.getJSON( ...
-
二叉树的递归遍历 The Falling Leaves UVa 699
题意:对于每一棵树,每一个结点都有它的水平位置,左子结点在根节点的水平位置-1,右子节点在根节点的位置+1,从左至右输出每个水平位置的节点之和 解题思路:由于上题所示的遍历方式如同二叉树的前序遍历,与 ...
-
【BZOJ1146】网络管理(主席树,树状数组)
[BZOJ1146]网络管理(主席树,树状数组) 题面 BZOJ权限题,洛谷题面 题解 树上带修改主席树 貌似和\(Count\ On\ A\ Tree\)那题很相似呀 只需要套上一个树状数组来维护修 ...
-
Android 1.7 中不支持 lambda 表达式
Error:(129, 32) 错误: -source 1.7 中不支持 lambda 表达式 (请使用 -source 8 或更高版本以启用 lambda 表达式) lambda expressio ...
-
[转载]如何在ubuntu上使用github
来源:https://blog.csdn.net/tina_ttl/article/details/51326684 https://blog.csdn.net/u013551462/article/ ...
-
Python链接Oracle数据库
说明:以下所需安装的所有软件版本必须跟系统一致,即系统是64位,软件就得是64位,否则会出现各种链接报错的情况. 现以64位系统,python 3.6.5 64位为例: (一)安装cx_Oracle ...
-
编译模块的Makefile解析
Makefile # if not defined KERNELRELEASE, command is running from command line,need invoke kbuild sys ...