bzoj 1001: [BeiJing2006]狼抓兔子 平面图最小割

时间:2022-03-08 21:51:37

平面图跑最大流 可以转换为其对偶图跑最短路 一个环对应一个割  找到最小环(即最短路)极为所求,注意辅助边的建立

加入读入优化  不过时间还是一般  估计是dij写的不好   大神勿喷~~~

/**************************************************************
Problem: 1001
User: 96655
Language: C++
Result: Accepted
Time:1724 ms
Memory:95120 kb
****************************************************************/ #include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<cstdlib>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#include<stack>
#include<utility>
using namespace std;
const int maxn=;
const int INF=0x3f3f3f3f;
struct Edge
{
int v,w,next;
} edge[maxn*];
int head[maxn*],p,n,m,y;
void addedge(int u,int v,int w)
{
edge[p].w=w;
edge[p].v=v;
edge[p].next=head[u];
head[u]=p++;
}
struct asd
{
int x,d;
asd (int a,int b):x(a),d(b) {}
bool operator<(const asd &e)const
{
return d>e.d;
}
};
priority_queue<asd>q;
int dis[maxn*],vis[maxn*];
void Dijkstra(int s)
{
memset(vis,,sizeof(vis));
while(!q.empty())q.pop();
for(int i=; i<=y; i++)
dis[i]=INF;
dis[s]=;
q.push(asd(s,));
while(!q.empty())
{
asd e=q.top();
q.pop();
if(vis[e.x])continue;
vis[e.x]=;
for(int i=head[e.x]; i!=-; i=edge[i].next)
{
int v=edge[i].v;
if(dis[v]>dis[e.x]+edge[i].w)
{
dis[v]=dis[e.x]+edge[i].w;
q.push(asd(v,dis[v]));
}
}
}
}
void read(int &x)
{
char c;
while((c=getchar())<'' || c>'');
x=c-'';
while((c=getchar())>='' && c<='') x=(x<<)+(x<<)+c-'';
}
int main()
{
read(n);
read(m);
if(n==||m==)
{
if(n>m)swap(n,m);
int ans=INF,a;
for(int i=; i<m; i++)
{
scanf("%d",&a);
ans=min(a,ans);
}
if(ans==INF)printf("0\n");
else printf("%d\n",ans);
return ;
}
memset(head,-,sizeof(head));
p=;
y=(n-)*(m-)*+;
int w,u,v;
for(int i=; i<=n; i++)
{
for(int j=; j<m; j++)
{
read(w);
if(i==)
{
u=((i-)*(m-)+j)*;
addedge(u,y,w);
addedge(y,u,w);
}
else if(i==n)
{
u=((i-)*(m-)+j)*-;
addedge(,u,w);
}
else
{
u=((i-)*(m-)+j)*;
v=((i-)*(m-)+j)*-;
addedge(u,v,w);
addedge(v,u,w); }
}
}
for(int i=; i<n; i++)
{
for(int j=; j<=m; j++)
{
read(w);
if(j==)
{
u=((i-)*(m-)+j)*-;
addedge(,u,w);
addedge(u,,w); }
else if(j==m)
{
u=((i-)*(m-)+j-)*;
addedge(u,y,w);
addedge(y,u,w); }
else
{
u=((i-)*(m-)+j)*-;
v=((i-)*(m-)+j-)*;
addedge(u,v,w);
addedge(v,u,w); }
}
}
for(int i=; i<n; i++)
{
for(int j=; j<m; j++)
{
read(w);
u=((i-)*(m-)+j)*-;
v=((i-)*(m-)+j)*;
addedge(u,v,w);
addedge(v,u,w);
}
}
Dijkstra();
printf("%d\n",dis[y]);
return ;
}

bzoj 1001: [BeiJing2006]狼抓兔子 平面图最小割的更多相关文章

  1. 【BZOJ】1001&colon; &lbrack;BeiJing2006&rsqb;狼抓兔子(最小割 &sol; 对偶图)

    题目 传送门:QWQ 分析 显然答案是最小割. 然后dinic卡一卡过去了. 其实是懒得写转对偶图:正解 (dinic原来写的是vector,后来改的比较鬼畜 代码 #include <bits ...

  2. BZOJ 1001 &lbrack;BeiJing2006&rsqb; 狼抓兔子(平面图最大流)

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

  3. BZOJ 1001&colon; &lbrack;BeiJing2006&rsqb;狼抓兔子【最大流&sol;SPFA&plus;最小割,多解】

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

  4. BZOJ 1001&colon; &lbrack;BeiJing2006&rsqb;狼抓兔子

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

  5. &lbrack;BZOJ1001&rsqb;&lbrack;BeiJing2006&rsqb;狼抓兔子(最小割转最短路&vert;平面图转对偶图)

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

  6. BZOJ 1001 &lbrack;BeiJing2006&rsqb;狼抓兔子 (UVA 1376 Animal Run)

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

  7. BZOJ 1001&colon; &lbrack;BeiJing2006&rsqb;狼抓兔子&lpar;最短路&rpar;

    平面图的最小割转化为对偶图的最短路(资料:两极相通——浅析最大最小定理在信息学竞赛中的应用) ,然后DIJKSTRA就OK了. ------------------------------------ ...

  8. BZOJ&lowbar;2001&lowbar;&lbrack;BeiJing2006&rsqb;狼抓兔子&lowbar;最小割转对偶图

    BZOJ_2001_[BeiJing2006]狼抓兔子 题意:http://www.lydsy.com/JudgeOnline/problem.php?id=1001 分析:思路同NOI2010海拔. ...

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

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

随机推荐

  1. MYSQL常用内置函数详解说明

    函数中可以将字段名当作变量来用,变量的值就是该列对应的所有值:在整理98在线字典数据时(http://zidian.98zw.com/),有这要一个需求,想从多音字duoyinzi字段值提取第一个拼音 ...

  2. &lbrack;转&rsqb;WEB开发者必备的7个JavaScript函数

    我记得数年前,只要我们编写JavaScript,都必须用到几个常用的函数,比如,addEventListener 和 attachEvent,并不是为了很超前的技术和功能,只是一些基本的任务,原因是各 ...

  3. 关于JDK的配置

    ① 安装官网下载的相应JDK安装包. 现在官网主推JDK8,JDK7以及更老的版本需要注册才能提供下载链接. ② 比如个人下载的jdk7-xxx.exe,安装路径为C:\Program Files\J ...

  4. 四、VMware Tools 安装 与 问题

    解决VMware Tools无法安装的问题 虚拟机上装win2kgho版的系统,安装VMware Tools时,遇到“VMware Tools installation cannot be start ...

  5. 跟我学机器视觉-HALCON学习例程中文详解-测量圆环脚宽间距

    跟我学机器视觉-HALCON学习例程中文详解-测量圆环脚宽间距 This example program demonstrates the basic usage of a circular meas ...

  6. 简述grub启动引导程序配置及命令行接口详解

    一.版本 grub:Grand Unified Bootloader grub 0.x:grub legacy grub 1.x:grub2 二.grub legacy 三个过程 stage1:安装在 ...

  7. 架构4(lvs lb集群解决方案二 lvs&plus;keepalived)

    keepalived 1.实现调度器的HA 2.对realserver做健康检测 3.动态维护ipvs路由表

  8. Python常用库大全,看看有没有你需要的

    作者:史豹链接:https://www.zhihu.com/question/20501628/answer/223340838来源:知乎著作权归作者所有.商业转载请联系作者获得授权,非商业转载请注明 ...

  9. Python中如何实现im2col和col2im函数(sliding类型)

    今天来说说im2col和col2im函数,这是MATLAB中两个内置函数,经常用于数字图像处理中.其中im2col函数在<MATLAB中的im2col函数>一文中已经进行了简单的介绍. 一 ...

  10. Amazon Seller Central is Temporarily Unavailable

    Seller Central is Temporarily Unavailable We apologize for the inconvenience. Our technical staff is ...