首页 > 代码库 > BZOJ 2007 NOI 2010 海拔 平面图最小割->最短路SPFA+pq
BZOJ 2007 NOI 2010 海拔 平面图最小割->最短路SPFA+pq
题目大意:给出一个城市各个道路的双向流量,城市的左上角的高度是0,城市的右下角的高度是1,若人流升高海拔就会消耗体力,问最小需要消耗多少体力。
思路:这道题才是真正的让我见识到了algorithm中的heap的强大。
分析这道题可以发现,一定会有一条分界线,这个分界线左边高度都为0,右边高度都是1,然后找到这条分界点就可以了。明显的最小割。但是数据量巨大,直接跑最大流会T,又是平面图,建立对偶图然后跑最短路,SPFA+pq在BZOJ上可以很快,如果有的OJ卡STL的话可以考虑SPFA+Heap,速度要比手写堆还要快。。
至于怎么建对偶图,可以画一张图模拟一下,自己看看就懂了,只要穿过一条边,高度由低变高,那么这条最短路图中的边的长度就是网络流中的边的流量。
CODE(HEAP_SPFA,很快):
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 510 #define MAXP 250010 #define MAXE 1501000 #define S 0 #define T (cnt + 1) using namespace std; struct Status{ int pos,len; Status(int _,int __):pos(_),len(__) {} Status() {} bool operator <(const Status &a)const { return len > a.len; } }; int m,cnt,num[MAX][MAX]; int head[MAXP],total; int next[MAXE],aim[MAXE],length[MAXE]; int f[MAXP]; bool v[MAXP]; inline void Add(int x,int y,int len) { next[++total] = head[x]; aim[total] = y; length[total] = len; head[x] = total; } void HEAP_SPFA() { static Status q[MAXE]; int size = 1; q[1] = Status(S,0); memset(f,0x3f,sizeof(f)); f[S] = 0; while(size) { pop_heap(q + 1,q + size + 1); Status now = q[size--]; int x = now.pos; if(now.len > f[x]) continue; for(int i = head[x]; i; i = next[i]) if(f[aim[i]] > f[x] + length[i]) { f[aim[i]] = f[x] + length[i]; q[++size] = Status(aim[i],f[aim[i]]); push_heap(q + 1,q + size + 1); } } } int main() { cin >> m; for(int i = 1; i <= m; ++i) for(int j = 1; j <= m; ++j) num[i][j] = ++cnt; for(int i = 1; i <= m; ++i) num[i][0] = T; for(int i = 1; i <= m; ++i) num[m + 1][i] = T; for(int i = 1; i <= m + 1; ++i) for(int x,j = 1; j <= m; ++j) { scanf("%d",&x); Add(num[i - 1][j],num[i][j],x); } for(int i = 1; i <= m; ++i) for(int x,j = 1; j <= m + 1; ++j) { scanf("%d",&x); Add(num[i][j],num[i][j - 1],x); } for(int i = 1; i <= m + 1; ++i) for(int x,j = 1; j <= m; ++j) { scanf("%d",&x); Add(num[i][j],num[i - 1][j],x); } for(int i = 1; i <= m; ++i) for(int x,j = 1; j <= m + 1; ++j) { scanf("%d",&x); Add(num[i][j - 1],num[i][j],x); } HEAP_SPFA(); cout << f[T] << endl; return 0; }
BZOJ 2007 NOI 2010 海拔 平面图最小割->最短路SPFA+pq
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。