首页 > 代码库 > BZOJ 2007 NOI2010 海拔 平面图最小割
BZOJ 2007 NOI2010 海拔 平面图最小割
题目大意:YT市是一个规划良好的城市,城市被东西向和南北向的主干道划分为n×n个区域。简单起见,可以将YT市看作一个正方形,每一个区域也可看作一个正方形。从而,YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路(简称道路),每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n = 2),城市被划分为2×2个区域,包括3×3个交叉路口和12条双向道路。 小Z作为该市的市长,他根据统计信息得到了每天上班高峰期间YT市每条道路两个方向的人流量,即在高峰期间沿着该方向通过这条道路的人数。每一个交叉路口都有不同的海拔高度值,YT市市民认为爬坡是一件非常累的事情,每向上爬h的高度,就需要消耗h的体力。如果是下坡的话,则不需要耗费体力。因此如果一段道路的终点海拔减去起点海拔的值为h(注意h可能是负数),那么一个人经过这段路所消耗的体力是max{0, h}(这里max{a, b}表示取a, b两个值中的较大值)。 小Z还测量得到这个城市西北角的交叉路口海拔为0,东南角的交叉路口海拔为1(如上图所示),但其它交叉路口的海拔高度都无法得知。小Z想知道在最理想的情况下(即你可以任意假设其他路口的海拔高度),每天上班高峰期间所有人爬坡所消耗的总体力和的最小值。
首先没有规定海拔高度是整数 所以很明显海拔两两不同这个条件可以无视了
容易发现答案一定是所有的0连在一起 1连在一起 中间有一条分界线 分界线上所有的边权和就是答案
直接最小割一定挂 考虑到这是平面图 所以我们建立对偶图 即左边界和下边界为起点 右边界和上边界为终点 所有被边围起来的区域是点 每条边沿中点逆时针旋转90° 跑一遍最短路即可
尼玛建图都没建错能把堆优化Dijkstra写挂我也是醉了
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 250500 #define S (n*n+1) #define T (n*n+2) using namespace std; struct abcd{ int to,f,next; }table[M<<2]; int head[M],tot; int n; int f[M],pos[M],heap[M],top; void Push_Up(int t) { while(t>1) { if(f[heap[t]]<f[heap[t>>1]]) swap(heap[t],heap[t>>1]), swap(pos[heap[t]],pos[heap[t>>1]]), t>>=1; else break; } } void Insert(int x) { heap[++top]=x; pos[x]=top; Push_Up(top); } void Pop() { pos[heap[1]]=0; heap[1]=heap[top--]; if(top) pos[heap[1]]=1; int t=2; while(t<top) { if(f[heap[t+1]]<f[heap[t]]) ++t; if(f[heap[t]]<f[heap[t>>1]]) swap(heap[t],heap[t>>1]), swap(pos[heap[t]],pos[heap[t>>1]]), t<<=1; else break; } } void Dijkstra() { int i; memset(f,0x3f,sizeof f);f[S]=0; for(i=1;i<=T;i++) Insert(i); while(top) { int x=heap[1];Pop(); for(i=head[x];i;i=table[i].next) if(f[table[i].to]>f[x]+table[i].f) f[table[i].to]=f[x]+table[i].f,Push_Up(pos[table[i].to]); } } void Add(int x,int y,int z) { table[++tot].to=y; table[tot].f=z; table[tot].next=head[x]; head[x]=tot; } int main() { int i,j,x; cin>>n; for(i=0;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&x); if(i==0) Add(i*n+j,T,x); else if(i==n) Add(S,i*n-n+j,x); else Add(i*n+j,i*n-n+j,x); } for(i=1;i<=n;i++) for(j=0;j<=n;j++) { scanf("%d",&x); if(j==0) Add(S,i*n-n+1,x); else if(j==n) Add(i*n-n+j,T,x); else Add(i*n-n+j,i*n-n+j+1,x); } for(i=0;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&x); if(i==0) Add(T,i*n+j,x); else if(i==n) Add(i*n-n+j,S,x); else Add(i*n-n+j,i*n+j,x); } for(i=1;i<=n;i++) for(j=0;j<=n;j++) { scanf("%d",&x); if(j==0) Add(i*n-n+1,S,x); else if(j==n) Add(T,i*n-n+j,x); else Add(i*n-n+j+1,i*n-n+j,x); } Dijkstra(); cout<<f[T]<<endl; }
BZOJ 2007 NOI2010 海拔 平面图最小割