魔族蝌蚪团(搬运)

魔族蝌蚪团(搬运)

题目背景

魔族蝌蚪团的科技很高，比如去草，自瞄，压树，激光炮线，锁零件等。

这次坦克世界领土战魔族蝌蚪团也参加了。

题目描述

网吧里有 $n$ 台电脑，有一位魔族蝌蚪团的团员用了第 $k$ 台电脑打领土，然后他们用电脑开了各种你想得到想不到的外挂。

因为360会连坐插件，所以网吧老板给你 $m$ 次要求，这些要求需要按照给定的顺序执行，每次要求魔族蝌蚪团将第 $u_i$ 和 $v_i$ 台电脑交换，这样这台开了外挂的电脑就可能会被交换到另一个位置上。

你其实是一名间谍，想让其他来网吧打领土的团炸团，所以你进行了暗箱操作：你可以拒绝执行其中的若干条要求，目的是让开挂了的电脑最终被交换到 $j$ 号位置。

由于360查外挂这次查的很严，所以请对于所有 $j∈[1,n]$ 求出最少需要拒绝执行多少操作，使得开了外挂的电脑最终被交换到在第 $j $ 个位置。

输入格式

第一行三个整数 $n$ ,$m$ , $k$ ，表示电脑个数，总操作次数和开了挂的电脑的初始位置。

下面 $m$ 行，每行两个正整数 $u_i$ , $v_i$，表示这次操作选择的两个位置。

输出格式

共一行 $n$ 个整数，第 $i$ 个整数表示使开了挂的电脑最终停留在该位置所需的最少拒绝执行次数。

若最终开了挂的电脑不可能停留在该位置，则输出 $−1$。

样例 #1

样例输入 #1

样例输出 #1

2 0 3 1 -1

提示

对于 $20%$ 的数据： $n≤20$

对于 $80%$ 的数据： $n≤1000$

对于 $100%$ 的数据： $n≤10^5$

设 $f_k$ 是我们的外挂电脑最后到达 $i$ 点最少需要拒绝的次数，初始化全是 $inf$,除了 $k$ 是 $0$ ,那么我们对于每次交换 $(x,y)$ ，如果我们两个位置都没有到过，那么其实这次交换就是无意义的，如果拒绝的次数相等，那就是拒绝了 $k$ 次留在$x$ ，然后这一次不拒绝换到 $y$ ，$y$ 换到 $x$ 同理，并不会影响。对于一方比较大的情况，此时我们希望留在较小的一方就需要拒绝掉这一次交换（显然是最优的，最差也是和先到较小的一方再不拒绝相等），而对于较大的一方，它可以先到较小的一方，再不拒绝这一次操作换到较大的地方：

if(f[y] > f[x]) f[y] = f[x],f[x] ++;
if(f[x] > f[y]) f[x] = f[y],f[y] ++;

#include<iostream>
#define for1(i,a,b) for(int i = a;i <= b; i++)
int f[100005],n,m,k,x,y;
int main()
{
	std::cin>>n>>m>>k;
	for1(i,1,n)f[i]=1e9+7;
	f[k]=0;
	for1(i,1,m)
	{
		std::cin>>x>>y;
		if(f[x]>f[y]) f[x]=f[y],++f[y];
		else if(f[y]>f[x]) f[y]=f[x],++f[x];
	}
	for1(i,1,n)printf("%d ",f[i]!=1e9+7?f[i]:-1);
}

顺带一提，成功水到题目原OJ 最短解和最优解