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):
#includeCODE(堆优化+SPFA,BZOJ上开了-O2,pq的效率比较高,3056ms,不开-O2的话会比不加优化的慢,慎用!):#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]); } }}
#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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年03月13日 11时45分23秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
老李分享:《Linux Shell脚本攻略》 要点(八)下
2019-04-21
CA自签名证书,并给服务器颁发证书
2019-04-21
交换机级联
2019-04-21
Linux-unit9
2019-04-21
MySQL练习题:综合面试题
2019-04-21
DNS and BIND
2019-04-21
ipv6——下一代因特网协议。
2019-04-21
linux cd命令
2019-04-21
对Windows Server 的DNS服务器进行数据库备份
2019-04-21
前端必须会的基本知识题目
2019-04-21
我的友情链接
2019-04-21
Java easycms版本1.0发布
2019-04-21
程序员必备算法,排列组合
2019-04-21
ubuntu安装docker
2019-04-21
NAT
2019-04-21
arailsdemo 5
2019-04-21
Xmind下载与安装
2019-04-21
bootstrap 模态框
2019-04-21
使用Figlet生成酷炫LOGO
2019-04-21
nfs
2019-04-21