社区讨论
求助 为什么只有第二个点错了 答案行数不对……
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 条回复,欢迎继续交流。
正在加载回复...