求助，P1285怎么调都过不去

LJY_ljy @ 2022-08-09 14:39:05

#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

*/

by LJY_ljy @ 2022-08-10 12:22:14

捞一下贴 & @ 一下巨佬

@陆麟瑞

@平衡树森林

@AC_Evil

@LHQing

@Rainy7

by 06ray @ 2022-08-10 16:14:25

你答案是构造方案错了还是算的差值不对? @ljy_ljy

by 06ray @ 2022-08-10 16:17:42

 cha[cnt] = team[cnt][1].size() - team[cnt][2].size();

这一行是不是要加绝对值？

by LJY_ljy @ 2022-08-11 14:49:57

@陆麟瑞

既有差值不对也有构造方案不对

但是我认为应该不用加上绝对值，因为+cha[cnt]就表示往Ans[1]里面加Team[cnt][1]往Ans[2]里面加Team[cnt][2]

（还有加上绝对值之后就变成79pts了）

by LJY_ljy @ 2022-08-21 11:50:08

@陆麟瑞

然后调了一下就变成87pts了，只有两组人员数目gap的WA了，没有“No Solution”的毛病了

#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 void 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) {
                printf("No solution");
                exit(0);
            }
        }
    }
}

inline bool illegal() {
    for (int i = 1; i <= n; i++) {
        if (!color[i]) {
            cnt++;
            dfs(i, 1);
            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

*/

by LJY_ljy @ 2022-08-21 11:51:15

@陆麟瑞

就是将 dfs 函数从bool变成了void就避免了“No Solution”的问题

也不知道为什么

by Anyakwi @ 2022-09-14 11:48:19

@LJY_ljy 所以为什么变成void就过了啊，我也有这个问题