题解：P6472 [COCI 2008/2009 #6] SLICICE

· · 题解

简单题。

先考虑 m=0 的情况怎么做。

发现此时就是个普及组构造题，我们对于每个人需求量奇偶性分类讨论。

当 a_i 为偶数时，随便跟一个人 PK 然后选择自己赢，进行 \frac{a_i}{2} 轮后就处理完这个人。

当 a_i 为奇数时，还是按照上面的方式处理直到还剩 1，由于题目保证有解，我们将所有剩下 1 的人按任意顺序两两配对即可。

然后我们这一步实质将题目中等于的限制转化为了不大于，因为只要题目限定的条件没用使得超过 a_i 那么剩下都能构造。于是考虑如何构造限制。

发现只有三种状态，考虑刻画。典型的想法是先预先假设每个 PK 都平局，然后反贪调整。发现改变对局情况等价于将某个对局 (x,y) 中将 a_x-1 并 a_y+1，反之亦然。发现这个过程非常形象，等价于把 a_x 的某个卡片移动到 a_y。于是问题转化为存在若干数与若干操作，每次操作限定两个点可以拿走一个放到另一个，求一种方案使得所有数最终都非负。

这个东西一眼网络流，负数就原点向该点连等于数的绝对值的边，正数就该点向汇点连等于这个数的边，然后一个操作就是双向的连接两个点，容量都为 1。于是跑网络流就解决了。

#include <bits/stdc++.h>
#define N 110
using namespace std;
int n, m, sum;
int a[N], id[N];
struct Edge { int nxt, v, w; }E[100010]; int hd[N], cnt = -1;
inline void adde(int u, int v, int w)
{
    E[++cnt] = { hd[u],v,w }; hd[u] = cnt;
    E[++cnt] = { hd[v],u,0 }; hd[v] = cnt;
}
int x[1010], y[1010];
int nw[N], dep[N];
int s, t;
inline bool bfs()
{
    memset(dep, 0, sizeof dep);
    queue<int> q;
    nw[s] = hd[s], dep[s] = 1, q.push(s);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int v, i = hd[u]; ~i; i = E[i].nxt)
            if (E[i].w && !dep[v = E[i].v])
                nw[v] = hd[v], dep[v] = dep[u] + 1, q.push(v);
    }
    return dep[t];
}
int dfs(int u, int sum)
{
    if (u == t) return sum;
    int res = 0, k;
    for (int v, i = nw[u]; ~i; i = E[i].nxt)
    {
        nw[u] = i;
        if (!sum) return res;
        if (E[i].w && dep[v = E[i].v] == dep[u] + 1) k = dfs(v, min(E[i].w, sum)), sum -= k, res += k, E[i].w -= k, E[i ^ 1].w += k;
    }
    return res;
}
vector<tuple<int, int, int>> vec;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int lst = 0;
int main()
{
    memset(hd, -1, sizeof hd);
    if (n == 1) return puts("0"), 0;
    cin >> n >> m, s = n + 1, t = n + 2;
    for (int i = 1; i <= n; i++) cin >> a[i];
    static int u, v;
    for (int i = 1; i <= m; i++) cin >> u >> v, x[i] = u, y[i] = v, a[u]--, a[v]--, adde(u, v, 1), adde(v, u, 1);
    for (int i = 1; i <= n; i++)
        if (a[i] < 0) adde(s, i, -a[i]), id[i] = cnt - 1;
        else adde(i, t, a[i]), id[i] = cnt - 1;
    int ans = 0;
    while (bfs()) ans += dfs(s, 1e9);
    for (int i = 1; i <= n; i++)
        if (a[i] < 0) assert(!E[id[i]].w), a[i] = 0;
        else a[i] = E[id[i]].w;
    for (int i = 1; i <= m; i++)
    {
        int w1 = E[4 * (i - 1)].w, w2 = E[4 * (i - 1) + 2].w;
        if (w1 == w2) vec.emplace_back(x[i], y[i], 1);
        else if (w2) vec.emplace_back(x[i], y[i], 0);
        else vec.emplace_back(x[i], y[i], 2);
    }
    for (int i = 1; i <= n; i++)
    {
        if (a[i] & 1)
            if (lst) vec.emplace_back(lst, i, 1), lst = 0;
            else lst = i;
        a[i] /= 2;
        while (a[i]) a[i]--, vec.emplace_back(i, (i == 1) ? 2 : 1, 2);
    }
    cout << vec.size() << '\n';
    for (auto [x, y, z] : vec) cout << x << ' ' << y << ' ' << z << '\n';
    return 0;
}