Mysterious Tree

#构造 #图论 #交互

题目描述

Mr. Ham is a very diligent hamster in USTC, and he always uses his weekends to deliver takeout to earn more money.

To maximize his delivery efficiency, he wants to write a program to find the shortest route.

Specifically, we can consider the city Hefei where Mr. Ham is located as an undirected graph with $n$ vertices and $m$ edges. Each edge has a congestion level $w$. Mr. Ham starts at vertex $1$ and wants to deliver the takeout to vertex $n$. Mr. Ham has found that the delivery time is always determined by the two edges with the highest congestion level along the path. Therefore, Mr. Ham defines the length of a path as the sum of the congestion levels of the two edges with the highest congestion level among the paths. When there is only one edge in the path, the length is defined as the congestion level of that edge.

Now, Mr. Ham wants to know the minimum length of the path from vertex $1$ to vertex $n$. Since Mr. Ham doesn’t know how to program, he has entrusted this task to you.

输入格式

Each test contains multiple test cases. The first line contains a single integer $t$ ($1\le t\le 250$) denoting the number of test cases.

For each test case, the first line contains one integer $n$ ($4\le n\le 1000$) denoting the number of vertices. It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

输出格式

You can ask at most $\lceil \frac{n}{2}\rceil +3$ questions in every test case. To ask a question, output a line of the form “? $u$ $v$” ($1\le u,v\le n$, $u\ne v$). Then you should read the response from standard input.

In response to the query, the interactor will output a line with a single integer: $1$ if there is an edge between $u$ and $v$ in the tree, or $0$ if there is no such edge.

To give your answer, print a line of the form “! 1” if you determined that the tree is a chain, or “! 2” if you determined that it is a star. The output of the answer is not counted towards the limit of $\lceil \frac{n}{2}\rceil +3$ queries.

After printing the answer, your program should process the next test case, or terminate if there are no more test cases.

After printing each line, do not forget to output end of line and flush the output. To do the latter, you can use fflush(stdout) or cout.flush() in C++, System.out.flush() in Java, or stdout.flush() in Python.

样例 #1

样例输入 #1

2
4

1

1

1

4

1

0

0

0

样例输出 #1

? 1 2

? 2 3

? 3 4

! 1

? 1 3

? 2 4

? 1 2

? 1 4

! 2

解题思路

首先可以先观察星和链的区别

$1.$ 星：

$2.$ 链：

可以发现，星的中心一定被所有的点连接，因此我们两两不重复枚举所有的点，分点数为奇数、偶数讨论：

$(1)$ 如果点数为偶数，那么如果是星，一定会有两点连接，因此不存在连接一定是链，反之为星。

$(2)$ 如果点数为奇数，并且没有发现连边，那么就把最后一个点和任意一个点询问，如果是星，那么这最后一个点就是中心点了，也就一定有连边。 反正，就为链。

$(3)$ 如果点数为奇数，并且存在连边，那么记录连边的那个两点$u,v$，再和任意一个其他点$i$，判断是否分别有连边，如果分别都没有连边，那么就是链。
如果有一个点存在$u-i$连边，那么就选连边的那个点$u$和另外一个没有使用过的点$j$，判断是否存在$u-j$连边，如果存在则为星，否则，就为链。

代码

const int N = 2e5 + 7;
int ask(int u, int v) {
	std::cout << "? " << u << " " << v << std::endl;
	int x;
	cin >> x;
	return x;
}
void solve() {
	int n;
	cin >> n;
	int u = -1, v = -1;
	for (int i = 1; i < n; i += 2) {
		int x = ask(i, i + 1);
		if (x) {
			u = i, v = i + 1;
			break;
		}
	}
	if ((n & 1) && u == -1) {
		int x = ask(1, n);
		if (x == 0) {
			std::cout << "! 1" << std::endl;
			return;
		}
		else {
			u = 1, v = n;
		}
	}
	if (u == -1) {
		std::cout << "! 1" << std::endl;
		return;
	}
	vector<int>st(n + 1);
	st[u] = st[v] = 1;
	for (int i = 1; i <= n; ++i) {
		if (st[i]) continue;
		st[i] = 1;
		int x = ask(u, i);
		if (!x) swap(u, v);
		x = ask(u, i);
		if (x == 0) {
			std::cout << "! 1" << std::endl;
			return;
		}
		for (int j = 1; j <= n; ++j) {
			if (st[j]) continue;
			int x = ask(u, j);
			if (x) {
				std::cout << "! 2" << std::endl;
				return;
			}
			else {
				std::cout << "! 1" << std::endl;
				return;
			}
		}
	}
}
 
signed main() {
	ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
};