社区讨论
求助,P1285怎么调都过不去
P1285[NEERC 2001] 队员分组参与者 3已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @lo8cc32j
- 此快照首次捕获于
- 2023/10/27 16:17 2 年前
- 此快照最后确认于
- 2023/10/27 16:17 2 年前
RT,84pts
CPP#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#define MAXN 110
using namespace std;
int T, n, color[MAXN], cnt, cha[MAXN];
bool G[MAXN][MAXN], dp[MAXN][MAXN];
int ans[MAXN][MAXN];
vector<int> team[MAXN][2];
priority_queue<int, vector<int>, greater<int> > Ans[2];
inline int read() {
register int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline bool dfs(int x, int co) {
team[cnt][co].push_back(x);
color[x] = co;
for (int i = 1; i <= n; i++) {
if (x != i && !(G[x][i] && G[i][x])) {
if (color[i] == 0) dfs(i, 3 - co);
else if (color[i] == co) return false;
}
}
return true;
}
inline bool illegal() {
for (int i = 1; i <= n; i++) {
if (!color[i]) {
cnt++;
if (!dfs(i, 1)) return false;
cha[cnt] = team[cnt][1].size() - team[cnt][2].size();
}
}
return true;
}
inline void out_put(int dif) {
int t = dif;
for (int i = cnt; i >= 1; i--) {
if (ans[i][t + n] == 1) {
for (int u = 0; u < team[i][1].size(); u++) Ans[0].push(team[i][1][u]);
for (int u = 0; u < team[i][2].size(); u++) Ans[1].push(team[i][2][u]);
t -= cha[i];
} else if (ans[i][t + n] == 2) {
for (int u = 0; u < team[i][1].size(); u++) Ans[1].push(team[i][1][u]);
for (int u = 0; u < team[i][2].size(); u++) Ans[0].push(team[i][2][u]);
t += cha[i];
}
}
printf("%d ", Ans[0].size());
while (!Ans[0].empty()) {
printf("%d ", Ans[0].top());
Ans[0].pop();
}
printf("\n%d ", Ans[1].size());
while (!Ans[1].empty()) {
printf("%d ", Ans[1].top());
Ans[1].pop();
}
printf("\n");
}
int main() {
n = read();
for (int i = 1; i <= n; i++) {
while (true) {
int x = read();
if (x == 0) break;
G[i][x] = true;
}
}
if (!illegal()) {
printf("No solution\n");
} else {
dp[0][n] = true;
for (int i = 1; i <= cnt; i++) {
for (int j = -n; j <= n; j++) {
if (dp[i - 1][j + n]) {
ans[i][j + cha[i] + n] = 1;
ans[i][j - cha[i] + n] = 2;
dp[i][j + cha[i] + n] = true;
dp[i][j - cha[i] + n] = true;
}
}
}
for (int i = 0; i <= n; i++) {
if (dp[cnt][i + n]) {
out_put(i);
break;
}
if (dp[cnt][-i + n]) {
out_put(-i);
break;
}
}
}
return 0;
}
/*
2
5
3 4 5 0
1 3 5 0
2 1 4 5 0
2 3 5 0
1 2 3 4 0
5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0
No solution
3 1 3 5
2 2 4
*/
回复
共 7 条回复,欢迎继续交流。
正在加载回复...