首页 > 其他分享 >P6628 [省选联考 2020 B 卷] 丁香之路 题解

P6628 [省选联考 2020 B 卷] 丁香之路 题解

时间:2024-11-13 16:58:03浏览次数:1  
标签:tmp 偶度 P6628 int 题解 fa fnd 联考 dis

P6628 [省选联考 2020 B 卷] 丁香之路 题解

首先考虑题目中路径权值的含义:\(i,j\) 两点之间的最短路就是 \(|i-j|\) 直接连边。

题目要求从 \(s\) 遍历到每个点,到终点每个 \(x\) 的最短时间。于是我们不妨枚举每个 \(x\),考虑在 \(O(n)\) 至 \(O(n\log n)\) 的时间复杂度里解决问题。

观察到题目的定义和欧拉回路的定义很相似。若加上 \((s,x)\) 的虚边,就是一个欧拉回路了。考虑欧拉回路的判定条件是所有点的度数都是偶数。于是我们的任务转变为了将存在的这些个奇度点通过连一些边的方式变成偶度点,同时要保证图联通。

偶度点的限制更不好处理一些,于是让我们先考虑偶度点的限制。在解决问题之前需要注意到本题中特殊权值带来的性质:对于 \(a,b\) 两点,最短路是 \(|a-b|\),于是不妨在 \(a,b\) 之间的每两个相邻的点之间都连一条边,这样不仅只改变了 \(a,b\) 点度数的奇偶性,还尽可能多地连通了连通块。

于是我们将所有奇度点排序为 \(a_1,a_2,a_3\cdots,a_n\),将 \(a_1,a_2;a_3,a_4\) 这样两两配对一定最优。对于连通性问题,首先容易发现的是上述的连边一定不劣,证明的话考虑无论如何奇度点会找到另一个奇度点配对,那对 \(a_1\),如果不找 \(a_2\),倘若找到 \(a_t\),那么这样更新的实质和 \(a_1\rightarrow a_2\rightarrow a_t\) 是一致的,依此类推地去考虑分析。那么现在的图都是偶度点,加一条边就必须加双向的。连边的原则仍然是尽量连相邻的边,于是将连续的两两不相邻的边加入最小生成树去跑即可。

时间复杂度的话是 \(O(n^2\log n)\) 的,瓶颈是最小生成树。

代码:

#include <bits/stdc++.h>
#define N 2505
#define int long long
using namespace std; 
int n, m, s;
int fa[N], fz[N];
int fnd(int x) {
	return x == fa[x] ? x : fa[x] = fnd(fa[x]);
}
void mge(int x, int y) {
	x = fnd(x), y = fnd(y);
	fa[x] = y;
}
int deg[N];
struct Node {
	int x, y, dis;
	bool operator < (const Node &a) const {
		return dis < a.dis;
	}
};
int ans, sum;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> s;
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		deg[x]++, deg[y]++;
		sum += abs(x - y);
		mge(x, y);
	}
	for (int i = 1; i <= n; i++)
		fz[i] = fa[i];
	for (int i = 1; i <= n; i++) {
		deg[s]++;
		deg[i]++;
		ans = sum;
		for (int j = 1; j <= n; j++)
			fa[j] = fz[j];
		int t = 0;
		for (int j = 1; j <= n; j++)
			if (deg[j] & 1) {
				if (t) {
					for (int k = t; k < j; k++)
						mge(k, k + 1);
					ans += j - t;
					t = 0;
				}
				else t = j;
			}
		vector<int>p;
		for (int j = 1; j <= n; j++)
			if (deg[j]) p.push_back(j);
		int l = p.size();
		vector<Node>v;
		for (int j = 1; j < l; j++)
			if (fnd(p[j - 1]) != fnd(p[j]))
				v.push_back({p[j - 1], p[j], p[j] - p[j - 1]});
		sort(v.begin(), v.end());
		for (auto tmp : v)
			if (fnd(tmp.x) != fnd(tmp.y))
				ans += tmp.dis << 1ll, mge(tmp.x, tmp.y);
		cout << ans << " ";
		deg[s]--;
		deg[i]--;
	}
	return 0;
}

标签:tmp,偶度,P6628,int,题解,fa,fnd,联考,dis
From: https://www.cnblogs.com/Rock-N-Roll/p/18544331

相关文章

  • 《统计每个月兔子的总数》 递归、记忆化数组、动态规划题解
    目录题目描述输入描述输出描述解析完整代码描述有一对兔子,从出生后第3个月起每个月都生一对兔子,一对小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问第n个月(n<=50)的兔子总数为多少对?输入描述输入1个整数n,表示第几个月输出描述第n个月兔子的总数量有多少?......
  • P10833 [COTS 2023] 下 Niz题解
    题意:给定长度为\(N\)的序列\(a\),求满足以下条件的\((l,r)\)对数:\(1\lel\ler\leN\);\(a_l,a_{l+1},\cdots,a_{r-1},a_r\)是\(1\simr-l+1\)的排列。\(1\leN\le10^6\);\(1\lea_i\leN\)。思路首先,“排列”本身这个性质是很强的。因为排列本身需要从1开......
  • AT_agc011_d [AGC011D] Half Reflector 题解
    用\(1\)表示A,\(0\)表示B,观察进行一次操作后字符串会发生什么变化。首先当第一个数为\(1\)时,只会将第一个数变为\(0\)。对于剩下的情况,手玩一下可以发现会将第一个数移到末尾,然后将所有数异或\(1\)。先考虑暴力怎么做,可以记一个指针\(i\)和当前应该给全体数异或的值\(......
  • P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces题解
    题意:给定一个长度为\(n=2^k\)的数组\(a\),下标从\(0\)开始,维护\(m\)次操作:给定\(x\),设数列\(a'\)满足\(a'_i=a_{i\oplusx}\),将\(a\)修改为\(a'\)。其中\(\oplus\)表示按位异或运算。给定\(l,r\),查询\(a\)的下标在\(l,r\)之间的子数组有多少颜色段。不保......
  • [题解]P3225 [HNOI2012] 矿场搭建
    P3225[HNOI2012]矿场搭建挖煤点坍塌相当于把该点和与其相连的边在图上删掉。借用wjyyy的题解,我们定义“叶子连通块”为“只包含\(1\)个割点的点双连通分量”,“非叶子连通块”为“包含\(\ge2\)个割点的点双连通分量”。如下图,橙色点是割点,红色框圈出的是点双,加粗的是叶子连通......
  • P2612 [ZJOI2012] 波浪 题解
    前置知识:连续段dp题目链接:P2612[ZJOI2012]波浪随机一个\(1\)到\(n\)的排列\(P_{1...n}\),问以下式子的值\(\lem\)的概率是多少?\[|P_1-P_2|+|P_2-P_3|+|P_3-P_4|+...+|P_{n-1}+P_n|\]输出一个答案表示概率。保留\(k\)位小数。对于\(40%\)......
  • P11071 「QMSOI R1」 Distorted Fate题解
    题意:给定一个序列,给定两种操作:将一个区间异或上一个给定的值。给定\(l,r\)求\[{\large(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}}\]\(0\lea_i,x<2^{30}\),\(1\lel\ler\len\)思路由于操作数以及区间过大,一位一位地去模拟肯定是不行的。因此考虑去离线......
  • [题解]CF1407D Discrete Centrifugal Jumps
    思路注意到第二个条件和第三个条件本质相似,可以用相同的维护方式处理,因此这个只讨论第二个条件的维护方式。定义\(dp_i\)表示走到\(i\)的最少步数。第一个条件的转移显然为\(dp_i\leftarrowdp_{i-1}\)。对于第二个条件,\(i\)能向\(j\)转移,当且仅当\(h_{i+1\sim......
  • Codeforces Round 985 div1+2 个人题解(A~E)
    CodeforcesRound985div1+2个人题解(A~E)Dashboard-Refact.aiMatch1(CodeforcesRound985)-Codeforces火车头#include<bits/stdc++.h>usingnamespacestd;#defineftfirst#definesdsecond#defineyescout<<"yes\n"#definenoc......
  • [CF1935E] Distance Learning Courses in MAC 题解
    [CF1935E]DistanceLearningCoursesinMAC难度正常的一道题。首先我们发现“挑选若干个区间”就是一句废话,因为按位或只会贡献答案而不会减小答案。所以我们需要在\([L,R]\)的每个区间都挑一个数,使得最终的按位或最大。想办法让尽可能多的二进制位都变成\(1\),且越是高......