BZOJ 3669 NOI 2014 魔法森林 最短路/LCT
发布日期:2021-10-02 10:57:31 浏览次数:31 分类:技术文章

本文共 3228 字,大约阅读时间需要 10 分钟。

题目大意:给一个无向图,每个边有两个权值,a和b,要想经过这条边,身上所携带的a和b都需要大于等于边的权值,否则就会遭到攻击。求从1到n身上携带最少的a+b的值

思路:1、LCT(不会)

            2、弱弱的用最短路。

利用SPFA求从起点到终点的最短最长距离是肯定能想到的,但是跑m次SPFA是肯定会超时的。

有一个十分神奇的想法,按照a的权值排序,从小到大一次将每一条边加入到图中,然后跑SPFA。dis数组不用清极大值,每次SPFA时只向队列里加入新加入的边的两个端点。这是两个很有效的剪枝。

CODE(不加堆优化,BZOJ3880ms):

#include 
#include
#include
#include
#include
#define MAX 600010#define INF 0x7f7f7f7fusing namespace std; queue
q; struct Complex{ int x,y; int a,b; bool operator <(const Complex& x)const { return a < x.a; }}edge[MAX]; int points,edges;int ans = INF;int head[MAX],total;int next[MAX],aim[MAX],length[MAX];int f[MAX];bool v[MAX]; inline void Add(int x,int y,int len);void SPFA(); int main(){ cin >> points >> edges; for(int i = 1;i <= edges; ++i) scanf("%d%d%d%d",&edge[i].x,&edge[i].y,&edge[i].a,&edge[i].b); sort(edge + 1,edge + edges + 1); memset(f,0x3f,sizeof(f)); f[1] = 0; for(int i = 1;i <= edges; ++i) { Add(edge[i].x,edge[i].y,edge[i].b); Add(edge[i].y,edge[i].x,edge[i].b); q.push(edge[i].x),v[edge[i].x] = true; q.push(edge[i].y),v[edge[i].y] = true; if(edge[i].a != edge[i + 1].a) SPFA(); ans = min(ans,edge[i].a + f[points]); } if(ans >= 0x3f3f3f3f) ans = -1; cout << ans; return 0;} inline void Add(int x,int y,int len){ next[++total] = head[x]; aim[total] = y; length[total] = len; head[x] = total; } void SPFA(){ while(!q.empty()) { int x = q.front(); q.pop(); v[x] = false; for(int i = head[x];i;i = next[i]) if(f[aim[i]] > max(length[i],f[x])) { f[aim[i]] = max(length[i],f[x]); if(!v[aim[i]]) q.push(aim[i]); } }}

CODE(堆优化+SPFA,BZOJ上开了-O2,pq的效率比较高,3056ms,不开-O2的话会比不加优化的慢,慎用!):

#include 
#include
#include
#include
#include
#define MAX 600010#define INF 0x7f7f7f7fusing namespace std; struct Point; priority_queue
q; struct Complex{ int x,y; int a,b; bool operator <(const Complex& x)const { return a < x.a; }}edge[MAX];struct Point{ int p; Point(int a):p(a) {} bool operator <(const Point& a)const;}; int points,edges;int ans = INF;int head[MAX],total;int next[MAX],aim[MAX],length[MAX];int f[MAX];bool v[MAX]; inline void Add(int x,int y,int len);void SPFA(); int main(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); cin >> points >> edges; for(int i = 1;i <= edges; ++i) scanf("%d%d%d%d",&edge[i].x,&edge[i].y,&edge[i].a,&edge[i].b); sort(edge + 1,edge + edges + 1); memset(f,0x3f,sizeof(f)); f[1] = 0; for(int i = 1;i <= edges; ++i) { Add(edge[i].x,edge[i].y,edge[i].b); Add(edge[i].y,edge[i].x,edge[i].b); q.push(Point(edge[i].x)),v[edge[i].x] = true; q.push(Point(edge[i].y)),v[edge[i].y] = true; if(edge[i].a != edge[i + 1].a) SPFA(); ans = min(ans,edge[i].a + f[points]); } if(ans >= 0x3f3f3f3f) ans = -1; cout << ans; return 0;} inline void Add(int x,int y,int len){ next[++total] = head[x]; aim[total] = y; length[total] = len; head[x] = total; } void SPFA(){ while(!q.empty()) { Point x = q.top(); q.pop(); v[x.p] = false; for(int i = head[x.p];i;i = next[i]) if(f[aim[i]] > max(length[i],f[x.p])) { f[aim[i]] = max(length[i],f[x.p]); if(!v[aim[i]]) q.push(Point(aim[i])); } }} bool Point :: operator <(const Point& a)const { return f[a.p] < f[p];}

转载地址:https://blog.csdn.net/jiangyuze831/article/details/39007565 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ 3670 NOI 2014 动物园 变形KMP
下一篇:BZOJ 3668 NOI 2014 Day1_T1 起床困难综合症 二进制拆分

发表评论

最新留言

很好
[***.229.124.182]2024年03月13日 11时45分23秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章