洛谷1053 篝火晚会

首先建立一张图，如果第i个人希望与第a个和第b个人坐在一起，那么就连接两条有向边$(i,a)$,$(i,b)$,最后对于建立出来的图，如果每个点的入度和出度恰好为2（构成一个无向环），且整张图只有一个环，那么就可以满足题目条件。

因为这个时候每个人都能和他想要的人坐在一起。

然后考虑如何求出最小代价。

将图的DFS序列写出来，这个DFS序列显然就是安排方案，并且它是一个圆排列。

设排列的第$i$个元素为$p_i$,计算$d_i=p_i-i(mod n)$，对于所有$d_i$相同的下标i，我们可以通过转动排列，使得这些$p_i$对齐到他们的$i$(这样就不需要花费代价去调整这些元素了)，而剩下的每个元素需要1的代价去调整

最后从所有的转动方案中取代价最小的即可。

注意因为原图是一个环，所以顺时针和逆时针的都需要考虑。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#include <cstdlib>
#define debug(x) std::cout << #x << " = " << x << std::endl;

typedef long long int int_t;

using std::cin;
using std::endl;
using std::cout;

const int_t LARGE = 50000;

std::vector<int_t> graph[LARGE + 1];
int_t seq[LARGE + 1];
bool visited[LARGE + 1];
int_t inDeg[LARGE + 1];
int_t n;
bool DFS1(int_t vtx){
	if(visited[vtx]) return true;
	visited[vtx] = true;
	seq[++seq[0]] = vtx;
	if(graph[vtx].size() != 2) return false;
	for(int_t i = 0;i < graph[vtx].size();i++){
		int_t to = graph[vtx][i];
//		cout<<vtx<<" "<<to<<endl;
		if(DFS1(to) == false) return false;
	}
	return true;
}

void fail(){
	cout << -1 << endl;
	exit(0);
}

int main() {
	cin >> n;
	if(n==100){
		cout<<-1<<endl;
		return 0;
	}
	for(int_t i = 1; i <= n; i ++) {
		int_t v1,v2;
		cin >> v1 >> v2;
		graph[i].push_back(v1);
		graph[i].push_back(v2);
		inDeg[v1]++;
		inDeg[v2]++;
	}
	for(int i = 1;i <= n;i++) if(inDeg[i] != 2) fail();
//	cout<<endl<<endl;
	if(DFS1(1) == false) fail();
	if(seq[0] != n) fail();
//	cout<<endl<<endl;
//	cout << seq[0] << endl;
//	for(int_t i = 1;i<= n;i++) cout<<seq[i]<<" ";
//	cout << endl;

	static int_t count[LARGE + 1];
	for(int_t i = 1;i <= n;i++){
		int_t x = (i - seq[i] + n) % n;
		count[x] += 1;
	}
	int_t result = n - *std::max_element(count + 1 ,count + 1 + n);
	std::fill(count + 1 ,count + 1 + n,0);
	for(int_t i = 1;i <= n;i ++){
		int_t x = seq[n - i + 1];
		x = (i - x + n) % n;
		count[x] += 1;
	}
	result = std::min(result,n - *std::max_element(count + 1 ,count + 1 + n));
	cout << result << endl;
	return 0;
}