「BalticOI 2015」Tug of War

传送门

一个月前的一道考试题。。。

如果我们把这 (2n) 个位置看成点，每个人看成一条边，然后连出对应的图，不难发现这是一个基环树森林。当然对于有的点没有边相连的情况一定是无解。

那么一个人选择站位就是每一条边匹配一条它的端点，由于构造出来的图是一个基环树森林，也就是说其实只有环上的边才有的选（而且一个环也只有两种不同的情况），子树上的边都是有唯一匹配的。

那么我们就可以把所有子树上的和各个环上的两类位置的 (s) 的总和统计出来。

然后我们不难发现题目就转化成了类似于这样的一道题。

其实就是一个背包模型，具体怎么背包请读者仔细解决。

但是我们是完全不可能去做一个 (O(n^2)) 级别的背包的。。。

这就不得不提到这道题的奇妙之处了

如果我们用多重背包的方式来背包，可以证明状态总数是在可承受时间范围内的。

然后就可以快乐地背包了 (Qomega Q)

参考代码：

#include <cstring>
#include <cstdio>
#include <cmath>

int max(int a, int b) { return a > b ? a : b; }
template < class T > void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
    s = f ? -s : s;
}

const int _ = 6e4 + 5, __ = 2e6 + 5;

int tot = 1, head[_]; struct Edge { int v, w, nxt; } edge[_ << 1];
void Add_edge(int u, int v, int w) { edge[++tot] = (Edge) { v, w, head[u] }, head[u] = tot; }

int n, K, a[_], va, top, stk[_], in[_], flag[_], vis[_ << 1], ok, sum1, sum2;
int m, cnt, w[_], c[__], dp[_ * 30];

void get(int u) {
    in[stk[++top] = u] = 1;
    for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].v; if (vis[i]) continue ;
        vis[i] = vis[i ^ 1] = 1;
        if (in[v]) { int x = top;
            do flag[stk[x]] = 1; while (stk[x--] != v);
        } else get(v);
    }
    in[stk[top--]] = 0;
}

void dfs(int u, int f) {
    for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].v; if (v == f || flag[v]) continue ;
        if (v <= n) sum1 += edge[i].w; else sum2 += edge[i].w;
        dfs(v, u);
    }
}

void calc(int u) {
    for (int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].v; if (vis[i] || !flag[v]) continue ;
        va ^= 1; va & 1 ? sum1 += edge[i].w : sum2 += edge[i].w;
        vis[i] = vis[i ^ 1] = 1;
        if (flag[v]) calc(v);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("cpp.in", "r", stdin), freopen("cpp.out", "w", stdout);
#endif
    read(n), read(K);
    for (int l, r, s, i = 1; i <= n << 1; ++i) {
        read(l), read(r), read(s), a[l] = a[r + n] = 1;
        Add_edge(l, r + n, s), Add_edge(r + n, l, s);
    }
    for (int i = 1; i <= n << 1; ++i) if (!a[i]) return puts("NO"), 0;
    for (int i = 1; i <= n << 1; ++i) get(i);
    for (int i = 1; i <= n << 1; ++i) if (flag[i]) dfs(i, 0);
    int mx = 0;
    ++c[w[++cnt] = 2 * abs(sum1 - sum2)], m += abs(sum1 - sum2), mx = max(mx, w[cnt]);
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n << 1; ++i)
        if (flag[i]) {
            sum1 = sum2 = 0, calc(i);
            if (sum1 && sum2)
                ++c[w[++cnt] = 2 * abs(sum1 - sum2)], m += abs(sum1 - sum2), mx = max(mx, w[cnt]);
        }
    memset(dp, 0, sizeof dp), dp[0] = 1;
    for (int i = 1; i <= mx; ++i)
        if (c[i])
            for (int j = m; j >= 0; --j)
                if (dp[j])
                    for (int x = 1; x <= c[i]; ++x)
                        if (j + x * i <= m && !dp[j + x * i]) dp[j + x * i] |= dp[j]; else break ;
    int ans;
    for (ans = m; ans >= 0; --ans) if (dp[ans]) break ;
    puts(m - ans <= K ? "YES" : "NO");
    return 0;
}