noip模拟赛多校第八场 T3 遥控机器人 (最短路 + 技巧拆点)

2023-11-06 20:30

本文主要是介绍noip模拟赛多校第八场 T3 遥控机器人 (最短路 + 技巧拆点),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题面

在这里插入图片描述

简要题意:
        给你一个 n n n 个点 m m m 条边的图。边 i i i 有颜色 c i c_i ci。你可以选择一些边改变它们的颜色成为区间 [ 1 , m ] [1, m] [1,m] 中的任意颜色,改变一条边 i i i 一次的代价是 w i w_i wi。询问你能否在一些改变操作后使得可以从 1 1 1 号点,每次只经过当前点的 特殊边 到达 n n n。特殊边的定义是 对于当前点而言,特殊边的颜色在该点所有出边中有且仅出现一条。 如果可以,输出最小代价。否则输出 − 1 -1 1

分析:

        凭感觉是一道最短路的题。

        首先有一个性质:因为颜色的区间与边数相同,所以如果要改变一条边,那么可以把它变成一个任何别的边都不会再变成的颜色。换言之, 如果要花费代价改变某一条边的颜色,那么可以把它变成无色,并且这样是最优的

        接下来我们考虑如果一条边 ( u , v ) (u, v) (u,v) 的颜色是 c c c,花费是 w w w。我们从 u u u v v v 经过它花费代价有几种情况:

        1. u u u 的出边中是 c c c 颜色的只有一条,那么代价是 0 0 0

        2. u u u 的出边中 c c c 颜色的边有多条,改变这条边的颜色至无色,花费是 w w w

        3. u u u 的出边中 c c c 颜色的边有多条,改变不改变它的颜色,改变其它边的颜色至无色。
            花费是 v a l u , c − w val_{u, c} - w valu,cw v a l u , c val_{u, c} valu,c 代表所有 u u u 的出边中颜色是 c c c 的边的代价之和。

        不难发现,情况 1 1 1 可以归到情况 3 3 3 中。

        我们考虑把这两种代价看做两种边权跑最短路会有什么问题:

        如果按照情况 3 3 3 u u u v v v,我们考虑会不会存在一个问题:按照情况 3 3 3 我们需要把其它颜色也为 c c c 的边都改成无色,那么把它变成无色但是却不记录会不会影响后面答案的计算呢?
)

        蓝色点表示最优路径的点,红色的边表示情况 3 3 3 中染成无色的边,它们的颜色是 c c c。黑色的边表示最优路径的边。那么如果出现上图的情况(从 5 5 5 号点走到 1 1 1 号点),那么 2 2 2 号点到 1 1 1 号点似乎是不需要花费的,因为在从 4 4 4 号点到 3 3 3 号点的时候就把那条颜色为 c c c 的边染成了无色。但是我们按照上面的规则进行的话,如果从 2 2 2 3 3 3 还使用情况 3 3 3,显然会多算一个代价。

        但是深入思考一下,这种情况不会发生。因为这样的路径一定不是最优路径。如果按照上图的走法,那么 ( 2 , 4 ) (2,4) (2,4) ( 6 , 4 ) (6, 4) (6,4) ( 4 , 7 ) (4, 7) (4,7) 的代价都会被算。实际上如果我们直接选择路径 5 → 4 → 2 → 1 5 \to 4 \to 2 \to 1 5421,并且 ( 4 , 2 ) (4, 2) (4,2) 使用情况 2 2 2 ( 2 , 1 ) (2, 1) (2,1) 使用情况 3 3 3 肯定更加优秀。

        这也就意味着: 如果我们能够通过某种方式处理好情况 2 2 2 带来的影响(即把边染成无色的影响),那么按照上面的规则跑最短路就是对的

        如果按照情况 2 2 2 经过一条颜色为 c c c 的边 从 u u u v v v,那么 ( u , v ) (u, v) (u,v) 这条边颜色的改变可能会影响从 v v v k k k 经过一条颜色为 c c c 按照情况 3 3 3 所花费的代价。根据这个问题,我们考虑 拆点

        有一个很暴力的想法是我们把每一个点拆成 m + 1 m + 1 m+1 个点:若有三个点 a a a, b b b , c c c a a a b b b 经过一条颜色为 x x x 的边,当使用情况 2 2 2 的时候,可以从 a a a 走向 b x b_x bx,代价为 0 0 0 b x b_x bx必须继续沿着颜色x使用情况 3 3 3 走向其他点。每一个点的 0 0 0 状态表示 没有限制。这样我们就解决了维护信息的问题。但是复杂度好像有点问题。

        我们考虑实际上一个点没有必要开 m m m 个点,只需要对每个点开其存在的颜色数个点就行了。一条边能够提供给两个点分别提供 1 1 1 个点,所以总点数是 2 m + n 2m + n 2m+n。然后建图跑最短路即可。时间复杂度 O ( ( n + m ) l o g 2 ( n + m ) ) O((n + m)log_2(n + m)) O((n+m)log2(n+m))。常数有亿点大。

CODE:

#include<bits/stdc++.h>//拆点   把点的状态拆一下 
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int T = 2 * N + M * 2;
typedef pair< int, int > PII;
typedef long long LL;
inline int read(){int x = 0, f = 1; char c = getchar();while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}while(isdigit(c)){x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}return x * f;
}
int u, v, c;
int n, m, head[T], ut[M], vt[M], ct[M], tot, len;//最多T个点
bool vis[T];
LL wt[M], dis[T], res, w; 
map< PII, int > rk;
map< PII, LL > val;
struct edge{int v, last;LL w;
}E[M * 8 + 10000];
void add(int u, int v, LL w){E[++len].v = v;E[len].last = head[u];E[len].w = w;head[u] = len;
}
struct state{int x; LL w;friend bool operator < (state a, state b){return a.w > b.w;}
};
void dijkstra(int s){priority_queue< state > q;q.push((state){s, 0});while(!q.empty()){state u = q.top(); q.pop();int x = u.x;if(vis[x]) continue;vis[x] = 1;for(int i = head[x]; i; i = E[i].last){int v = E[i].v; LL w = E[i].w;if(dis[v] > dis[x] + w){dis[v] = dis[x] + w;q.push((state){v, dis[v]});}}}
}
int main(){n = read(), m = read();for(int i = 1; i <= n; i++){rk[make_pair(i, 0)] = ++tot;}for(int i = 1; i <= m; i++){u = read(), v = read(); c = read(), w = 1LL * read();if(!rk[make_pair(u, c)]) rk[make_pair(u, c)] = ++tot;if(!rk[make_pair(v, c)]) rk[make_pair(v, c)] = ++tot;val[make_pair(u, c)] += w;val[make_pair(v, c)] += w;ut[i] = u, vt[i] = v, wt[i] = w, ct[i] = c;}for(int i = 1; i <= m; i++){int u = ut[i], v = vt[i], c = ct[i], w = wt[i];add(rk[make_pair(u, 0)], rk[make_pair(v, 0)], w);//改变颜色,不做限制 add(rk[make_pair(u, 0)], rk[make_pair(v, c)], 0);//改变颜色,必须限制 add(rk[make_pair(u, c)], rk[make_pair(v, 0)], val[make_pair(u, c)] - w);add(rk[make_pair(u, 0)], rk[make_pair(v, 0)], val[make_pair(u, c)] - w);add(rk[make_pair(v, 0)], rk[make_pair(u, 0)], w);//改变颜色,不做限制 add(rk[make_pair(v, 0)], rk[make_pair(u, c)], 0);//改变颜色,必须限制 add(rk[make_pair(v, c)], rk[make_pair(u, 0)], val[make_pair(v, c)] - w);add(rk[make_pair(v, 0)], rk[make_pair(u, 0)], val[make_pair(v, c)] - w);}memset(dis, 0x3f, sizeof dis);dis[rk[make_pair(1, 0)]] = 0;dijkstra(rk[make_pair(1, 0)]);res = dis[rk[make_pair(n, 0)]];if(res == 0x3f3f3f3f3f3f3f3f) res = -1;printf("%lld\n", res);return 0;
}

这篇关于noip模拟赛多校第八场 T3 遥控机器人 (最短路 + 技巧拆点)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/358885

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

poj 3255 次短路(第k短路) A* + spfa 或 dijkstra

题意: 给一张无向图,求从1到n的次短路。 解析: A* + spfa 或者 dijkstra。 详解见上一题:http://blog.csdn.net/u013508213/article/details/46400189 本题,spfa中,stack超时,queue的效率最高,priority_queue次之。 代码: #include <iostream>#i