社区讨论

求助,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 条回复,欢迎继续交流。

正在加载回复...