【BZOJ】2007: [Noi2010]海拔(平面图转对偶图)
2024-08-27 20:03:53
题目
传送门:QWQ
分析
左上角是0,右下角是1。那么大概整张图是由0 1构成的。
那么我们要找到0和1的分界线,值就是最小割。
然后变成求原图最小割。
考虑到此题是平面图,那么就转成对偶图跑最短路。
完了。
总结:以后看到数据在$ nlog(n) $范围内的题,给的图是方格图,给的边还方方正正,那么多半是平面图转对偶图。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=*;
vector<int> G[maxn];
struct Edge{ int u,v,dis; };
vector<Edge> edges;
struct HeapNode{
int x,dis;
bool operator <(const HeapNode& a) const{ return dis>a.dis; }
};
void link(int u,int v,int dis){
edges.push_back((Edge){u,v,dis}); //edges.push_back((Edge){v,u,dis});
int m=edges.size(); G[u].push_back(m-);
}
int d[maxn],vis[maxn];
priority_queue<HeapNode> que;
int dijkstra(int s,int t){
memset(d,,sizeof(d));
d[s]=; que.push((HeapNode){s,}); //vis[s]=1;
while(!que.empty()){
HeapNode x=que.top(); que.pop();
if(vis[x.x]) continue; vis[x.x]=;
int u=x.x;
for(int i=;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(d[e.v]>d[u]+e.dis){
d[e.v]=d[u]+e.dis;
que.push((HeapNode){e.v,d[e.v]});
}
}
}
return d[t];
}
int num[][];
int main(){
int n,x;scanf("%d",&n);
int s = , t = n * n + ;
for(int i = ; i <= n ; i ++ )
num[][i] = num[i][n + ] = s , num[i][] = num[n + ][i] = t;
for(int i=; i <= n ; i ++ )
for(int j = ; j <= n ; j ++ )
num[i][j] = n * (i - ) + j;
for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&x),link(num[i][j] , num[i+][j] , x);
for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&x),link(num[i][j+] , num[i][j] , x);
for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&x),link(num[i+][j] , num[i][j] , x);
for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&x),link(num[i][j] , num[i][j+] , x);
printf("%d\n",dijkstra(s,t));
return ;
}
最新文章
- redis集成到Springmvc中及使用实例
- 3种方法快速制作tpk文件 [转]
- 如何将本地项目与coding.net/github上的项目绑定
- 15,SFDC 管理员篇 - 变更和部署
- expr
- V​S​2​0​1​2​快​捷​键
- python(一)入门
- poj3062---输入什么输出什么
- [Android学习笔记]ShareSDK的使用
- C#读取和写入文件
- 数据结构(C语言版)顺序表相关算法代码实现
- hadoop集群篇--从0到1搭建hadoop集群
- Extensions in UWP Community Toolkit - Visual Extensions
- NewLife.Net——构建可靠的网络服务
- 「LOJ 2289」「THUWC 2017」在美妙的数学王国中畅游——LCT&;泰勒展开
- [Ubuntu] 运行.AppImage格式文件
- eclipse 安装插件报错问题
- 【转】XSHELL下直接下载文件到本地(Windows)
- HDU 1517 (累乘 找规律)
- 安装虚拟环境virtualenvwrapper和django
热门文章
- EasyPlayer RTSP Windows(with ActiveX/OCX插件)播放器支持H.265播放与抓图功能
- Mac安装三方软件
- IOS开发 __weak与__block修饰符到底有什么区别
- Python源码分析(二) - List对象
- 让thinkphp 5 支持pathinfo 的 nginx ,去掉index.php
- [BZOJ5361][Lydsy1805月赛]对称数
- SpringMVC传递数据的流线图
- Apache + Tomcat + 连接器JK
- 12.Python使用requests发送post请求
- 关于tab的切换之共用html页面,而引发的页面跳转错乱问题