AcWing 259. 真正的骗子

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 259. 真正的骗子原题链接困难

作者：

song666 , 2020-06-26 22:27:47 , 所有人可见 , 阅读 828

4

1

分析

这个题目比较难，一开始用扩展域，发现太难写就弃了
注意到回答yes的两个人同种；回答no的两个人不同类
因此可以使用并查集缩点，再染色求出二分图左右点的数量
然后跑可行性背包即可

算法

(二分图+并查集+背包) $O(n^2\log n)$

这个题目应该是遇到的最难的并查集题目了
先处理yes询问，把同种人用并查集缩点
用no询问分开不同的人(在代表集合之间连边)，得到二分图
跑一遍染色法，求出左右两部分点的大小。
再跑计数性背包，求出n个人中有p1个天神的方案数
最后逆推，输出方案，本题即可得到完美解决

时间复杂度

背包+vector输出方案+染色法+并查集，$O(n^2\log n)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 1010

using namespace std;

int n, m, p1, p2;
int a[maxn], b[maxn];
string c[maxn];
int p[maxn], sz[maxn];
int h[maxn], e[maxn * 2], ne[maxn * 2], col[maxn], idx;
int v[maxn][2], tot;
bool st[maxn];
vector<int> g[maxn][2];
int f[maxn][maxn];

int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; }
void dfs(int u, int c)
{
    v[tot][c] += sz[u];
    g[tot][c].push_back(u);
    col[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (col[j] != -1) continue;
        dfs(j, c ^ 1);
    }
}

void TrueLiars()
{
    tot = 0, idx = 0;
    memset(st, 0, sizeof st);
    memset(h, -1, sizeof h);
    memset(v, 0, sizeof v);
    memset(f, 0, sizeof f);
    memset(col, -1, sizeof col);
    n = p1 + p2;
    for (int i = 1; i < maxn; i ++ ) g[i][0].clear(), g[i][1].clear();

    for (int i = 1; i <= m; i ++ ) cin >> a[i] >> b[i] >> c[i];
    for (int i = 1; i <= n; i ++ ) p[i] = i, sz[i] = 1;
    for (int i = 1; i <= m; i ++ )
        if (c[i] == "yes")
            if (find(a[i]) != find(b[i]))
            {
                sz[find(b[i])] += sz[find(a[i])];
                p[find(a[i])] = find(b[i]);
            }
    for (int i = 1; i <= m; i ++ )
        if (c[i] == "no")
            add(find(a[i]), find(b[i])), add(find(b[i]), find(a[i]));

    for (int i = 1; i <= n; i ++ )
        if (find(i) == i && col[i] == -1)
        {
            tot ++ ;
            dfs(i, 0);
        }

    f[0][0] = 1;
    for (int i = 0; i < tot; i ++ )
        for (int j = 0; j <= n; j ++ )
            if (f[i][j])
            {
                f[i + 1][j + v[i + 1][0]] += f[i][j];
                f[i + 1][j + v[i + 1][1]] += f[i][j];
            }

    if (f[tot][p1] != 1) puts("no");
    else
    {
        int j = p1;
        for (int i = tot; i >= 1; i -- )
            if (f[i - 1][j - v[i][0]] == 1)
            {
                j -= v[i][0];
                for (auto x : g[i][0]) st[x] = true;
            }
            else if (f[i - 1][j - v[i][1]] == 1)
            {
                j -= v[i][1];
                for (auto x : g[i][1]) st[x] = true;
            }
        for (int i = 1; i <= n; i ++ )
            if (st[i])
            {
                for (int j = 1; j <= n; j ++ )
                    if (find(j) == i) st[j] = true;
            }

        for (int i = 1; i <= n; i ++ )
            if (st[i]) cout << i << endl;
        puts("end");
    }
}

int main()
{
    while (cin >> m >> p1 >> p2 && (m || p1 || p2)) TrueLiars();

    return 0;
}