社区讨论

求助 为什么只有第二个点错了 答案行数不对……

P1963[NOI2009] 变换序列参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mi6o8nhc
此快照首次捕获于
2025/11/20 08:06
4 个月前
此快照最后确认于
2025/11/20 08:06
4 个月前
查看原帖
CPP
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define v1 (i+d)%n
#define v2 (i-d+n)%n
inline int read() {
	int s = 0, f = 1; char c = getchar(); while (c<'0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0'&&c <= '9') { s = s * 10 + c - '0'; c = getchar(); }
	return s*f;
}
int n;
const int maxn = 10007;
vector<int> g[maxn << 1];
bool vis[maxn << 1];
int link[maxn << 1],ans[maxn<<1];
bool dfs(int u) {
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (!vis[v]) {
			vis[v] = true;
			if (link[v]==-1 || dfs(link[v])) {
				link[v] = u;
				ans[u] = v;
				return true;
			}
		}
	}
	return false;
}
int hungary() {
	int res = 0;
	memset(link, -1, sizeof(link));
	for (int i = n - 1; i >= 0; i--) {
		memset(vis, false, sizeof(vis));
		if (!dfs(i)) {
			puts("No Answer");
			return -1;
		}
		res++;
	}
	//printf("%d\n", res);
	return res;
}
int main() {
	n = read();
	int d;
	for (int i = 0; i < n; i++) {
		d = read();
		g[i].push_back(v1);
		g[i].push_back(v2);
	}
	for (int i = 0; i < n; i++) sort(g[i].begin(), g[i].end());
	//保证在dfs过程中先考虑较小的那个点
	if (hungary() == n) {
		for (int i = 0; i < n - 1; i++)
			printf("%d ", ans[i]);
		printf("%d", ans[n - 1]);
	}
	else {
		puts("No Answer");
	}
	//getchar();
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...