「UOJ-171」【WC2016】挑战NPC(一般图匹配带花树)

发表于 | 分类于 ，

「UOJ-171」【WC2016】挑战NPC

题意

有$n$个球和$m$个筐，每个球可以放入与其连边的某个筐，每个筐最多放三个球。将所有球放入筐中，筐中不超过一个球时称为「半满」，需要使半满的框数最多，并输出其中一种方案数。

题解

把一个筐拆成三个点，三个点之间两两连边。将可以放入某个框中的球向框的三个点连边，跑一遍带花树，$n-maxmatch$即为最大值。

因为对于某一个筐的三个点来说：球数为0时最大匹配为1，球数为1时最大匹配为2，球数为2和3时最大匹配为2。

那么对于这个筐，它对答案的贡献即为（最大匹配数-球数），输出方案即可。

注意求解时要先匹配球，否则会先匹配同一个筐与筐之间的连边，这样求出的方案就不对了orz。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000 + 10;

vector<int> edge[maxn];
queue<int> que;

int n, pre[maxn], type[maxn], link[maxn], nex[maxn], vis[maxn];

void add(int u, int v)
{
    edge[u].push_back(v);
    edge[v].push_back(u);
}

int Find(int x)
{
    return x == pre[x] ? x : pre[x] = Find(pre[x]);
}

void combine(int x, int lca)    //如果找到奇环，对当前点x和找到的
{
    while (x != lca)
    {
        int u = link[x], v = nex[u];
        if (Find(v) != lca) nex[v] = u;
        if (type[u] == 1) type[u] = 2, que.push(u);
        pre[Find(x)] = Find(u);
        pre[Find(u)] = Find(v);
        x = v;
    }
}

void contrack(int x, int y)
{
    int lca = x;
    memset(vis, 0, sizeof(vis));
    for (int i = x; i; i = nex[link[i]])
    {
        i = Find(i);
        vis[i] = 1;
    }
    for (int i = y; i; i = nex[link[i]])
    {
        i = Find(i);
        if (vis[i])
        {
            lca = i;
            break;
        }
    }
    if (lca != Find(x)) nex[x] = y;
    if (lca != Find(y)) nex[y] = x;
    combine(x, lca);
    combine(y, lca);
}

void bfs(int s)
{
    memset(type, 0, sizeof(type));
    memset(nex, 0, sizeof(nex));
    for (int i = 1; i <= n; i++) pre[i] = i;
    while (!que.empty()) que.pop();
    que.push(s);
    type[s] = 2;
    while (!que.empty())
    {
        int x = que.front();
        que.pop();
        for (int i = 0; i < edge[x].size(); i++)
        {
            int y = edge[x][i];
            if (Find(x) == Find(y) || link[x] == y || type[y] == 1) continue;
            if (type[y] == 2) contrack(x, y);
            else if (link[y])
            {
                nex[y] = x;
                type[y] = 1;
                type[link[y]] = 2;
                que.push(link[y]);
            } else
            {
                nex[y] = x;
                int pos = y, u = nex[pos], v = link[u];
                while (pos)
                {
                    link[pos] = u;
                    link[u] = pos;
                    pos = v;
                    u = nex[pos];
                    v = link[u];
                }
                return;
            }
        }
    }
}

int maxmatch()
{
    for (int i = n; i >= 1; i --) if (!link[i]) bfs(i);
    int ans = 0;
    for (int i = n; i >= 1; i --) if (link[i]) ans++;
    return ans / 2;
}

void init()
{
    for (int i = 1; i <= n; i++) edge[i].clear();
    memset(link, 0, sizeof(link));
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        int N, m, e;
        scanf("%d%d%d", &N, &m, &e);
        n = 3 * m + N;
        init();
        for(int i = 1; i <= 3 * m; i += 3)
        {
            add(i, i + 1);
            add(i, i + 2);
            add(i + 1, i + 2);
        }
        int u, v;
        while(e --)
        {
            scanf("%d%d", &u, &v);
            add(u + 3 * m, (v - 1) * 3 + 1);
            add(u + 3 * m, (v - 1) * 3 + 2);
            add(u + 3 * m, (v - 1) * 3 + 3);
        }
        printf("%d\n", maxmatch() - N);
        for(int i = 1 + 3 * m; i <= n; i ++)
            printf("%d%c", (link[i] - 1) / 3 + 1, " \n"[i == n]);
    }
    return 0;
}