1

题目描述

赛场内 n (0<n≤10) 名短跑运动员正在参加百米短跑比赛。赛场外有 m (0<m≤100) 名热心观众，他们每人都对比赛结果作出了 2 个预测。比赛结束后，运动员的名次各不相同，但令人惊奇的是每位观众都猜对了一半。请问这些运动员取得的实际名次是多少？

例如场内有 4 名运动员参加比赛，场外 3 名观众的预测分别为：

  • 1 号运动员名次为 1，2 号运动员名次为 3
  • 3 号运动员名次为 1，4 号运动员名次为 4
  • 4 号运动员名次为 2，1 号运动员名次为 3

由每人猜对一半推理可知：

  • 1 号运动员名次为 4
  • 2 号运动员名次为 3
  • 3 号运动员名次为 1
  • 4 号运动员名次为 2

请编写程序，根据观众的预测来推算运动员的实际名次。

输入格式

两个正整数 n 和 m (运动员人数、观众人数)
随后有 m 行数据，每行包含 4 个整数，为 m 位观众的预测
每行包含的 4 个整数 x1、r1 和 x2、r2 表示该观众的两个预测：
x1 号运动员名次为 r1，x2 号运动员名次为 r2

说明：

  • n 名运行员的编号为从 1 到 n 的正整数，无重号和跳号。
  • n 名运动员的名次为从 1 到 n 的正整数，无并列的情况。

输出格式

若问题无解，则输出 None。
若问题有解，则输出多行数据，每一行表示一个答案，按字典序输出。
每一行包含 n 个整数，分别是 1 ~ n 号运动员取得的实际名次。

样例 #1

样例输入 #1

1
2
3
4
4 3
1 1 2 3
3 1 4 4
4 2 1 3

样例输出 #1

1
4 3 1 2

样例输入 #2

1
2
3
4
4 3
3 4 2 1
4 3 3 2
1 4 2 3

样例输出 #2

1
None

样例输入 #3

1
2
3
4
4 3
2 4 4 1
4 2 2 3
3 4 1 1

样例输出 #3

1
2
1 4 3 2
2 3 4 1

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <algorithm>
using namespace std;

int audienceGuess[101][5];//观众猜测
bool guessTrue[11];//猜测成立
int n, m;
int ansSchemes;//结果数量 10! = 3628800

struct {
	int rank;
	int failNum;
	int guess[101];
}athletes[11];
//rank[]为每个方案运动员的名次，sum保存每个方案运动员名次的十进制整数 
struct Guess {
	int rank[11];
} ans[368800];

bool checkRank(int index, int rank) {
	int i;
	for (i = 0; i < athletes[index].failNum; i++) {
		if (athletes[index].guess[i] == rank) {
			return false;
		}
	}
	return true;
}

void fix(int index) {//回溯法把剩余没有名次的运动员根据约束条件补齐 
	if (index > n) {
		//保存其中一种结果
		for (int i = 1; i <= n; i++) {
			ans[ansSchemes].rank[i] = athletes[i].rank;
		}
		ansSchemes++;
	}
	else {

		//当前运动员没有名次
		if (athletes[index].rank == 0) {
			for (int i = 1; i <= n; i++) {
				if (!guessTrue[i] && checkRank(index, i)) {//名次i未被标记且第index个运动员的名次i不在假名次中 
					athletes[index].rank = i;
					guessTrue[i] = true;
					fix(index + 1);
					athletes[index].rank = 0;
					guessTrue[i] = false;
				}
			}
		}
		else {
			fix(index + 1);
		}
	}
}

//嗨嗨嗨，回溯
void assump(int index) {
	if (index < m) {
		//index号预测情况模拟
		//真 假 i = 0
		//假 真 i = 1
		for (int i = 0; i < 2; i++) {
			//两位观众预测相同
			int gsI1 = 1 + 2 * i, gsI2 = 2 + 2 * i;
			int gsI3 = 3 - 2 * i, gsI4 = 4 - 2 * i;
			if (athletes[audienceGuess[index][gsI1]].rank == audienceGuess[index][gsI2]) {
				if (checkRank(audienceGuess[index][gsI3], audienceGuess[index][gsI4])) {
					athletes[audienceGuess[index][gsI3]].
						guess[athletes[audienceGuess[index][gsI3]].failNum] = audienceGuess[index][gsI4];
					athletes[audienceGuess[index][gsI3]].failNum++;

					assump(index + 1);

					athletes[audienceGuess[index][gsI3]].
						guess[athletes[audienceGuess[index][gsI3]].failNum] = 0;
					athletes[audienceGuess[index][gsI3]].failNum--;
				}
				else {
					assump(index + 1);
				}
			}
			//两位观众预测不相同
			else {
				if ((!guessTrue[audienceGuess[index][gsI2]] &&
					athletes[audienceGuess[index][gsI1]].rank == 0 &&
					checkRank(audienceGuess[index][gsI1], audienceGuess[index][gsI2])
					) || index == 0) {
					athletes[audienceGuess[index][gsI1]].rank = audienceGuess[index][gsI2];
					guessTrue[audienceGuess[index][gsI2]] = true;
					athletes[audienceGuess[index][gsI3]].
						guess[athletes[audienceGuess[index][gsI3]].failNum] = audienceGuess[index][gsI4];
					athletes[audienceGuess[index][gsI3]].failNum++;

					assump(index + 1);

					athletes[audienceGuess[index][gsI1]].rank = 0;
					guessTrue[audienceGuess[index][gsI2]] = false;
					athletes[audienceGuess[index][gsI3]].
						guess[athletes[audienceGuess[index][gsI3]].failNum] = 0;
					athletes[audienceGuess[index][gsI3]].failNum--;
				}
			}
		}
	}
	else if (index == m) {
		fix(1);
	}
}

int cmp(const Guess& a, const Guess& b) {
	int suma = 0, sumb = 0;
	for (int i = 1; i <= n; i++) {
		suma = suma * 10 + a.rank[i];
		sumb = sumb * 10 + b.rank[i];
	}
	return suma > sumb;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> audienceGuess[i][1] >> audienceGuess[i][2] >> audienceGuess[i][3] >> audienceGuess[i][4];
	}

	assump(0);

	if (ansSchemes == 0) {
		cout << "None";
		goto end;
	}

	sort(ans, ans + ansSchemes - 1, cmp);

	for (int i = 0; i < ansSchemes; i++) {
		if (i)cout << endl;
		for (int j = 1; j <= n; j++) {
			if (j > 1)cout << " ";
			cout << ans[i].rank[j];
		}
	}
end:;
	return 0;
}