[BalticOI 2015]Tug of War

· · 题解

Solution:

这题楼上已经讲得很清楚了，就是考虑将人看成边去连接两个点，将点分配给边获得相应的权值。有解当且仅当连出来的图是一个基环树森林。

而基环树森林是方便将点分配给边的。因为对于树的部分，方案已经确定。对于环的部分，分配分成顺时针和逆时针两种情况。而在这一道题中，因为一条边肯定连接的是左边和右边，得到的是一个偶环，也就是说，顺时针分配得到的权值和逆时针分配得到的权值是相反数。

因为要求得两边的权值差在 k 内是否有解，这个问题结合上这个基环树森林可以用背包解决。可以先假定都取顺时针顺序，然后用逆时针顺序减去顺时针顺序作为权值去做，但复杂度为 O(\frac {n^2a}{w}) 。另外一篇题解好像是用这个不正确的复杂度通过的。

注意到做的是背包，并且总权值是 na 的，可以得知不同的个数在 \sqrt{na} 内，做多重背包就好了。单调队列没法 bitset 优化，所以使用二进制分组。但是需要注意的是，二进制分组在这里的复杂度是 O(\frac{na\sqrt{na}}{w}) 的而非楼上题解所写的是 O(\frac{na\sqrt{na}log(\sqrt{na})}{w})。

因为这里的 log 并不能简单的写成 log(na)，复杂度应该写成 \frac{na\sum_i^{cnt}log(b_i)}{w} ，其中 cnt 是不同权值的个数，b_i 是第 i 个权值的个数。其中满足 \sum_i^{cnt}b_i*val_i \le na。这个东西实际上是可以被证明是常数。

code: 

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 10;
int n, k, m, bas;
int c[N];
int first[N], nex[N << 1], v[N << 1], w[N << 1], num = 1;
int vis[N], cir[N], sav[N], stu[N], top = 0; 
int val[N], len[N], cnt = 0;
struct node {
    int val, cnt;
}a[N];
int edg = 0, ver = 0;
bitset<N * 20> dp;
inline void add(int x, int y, int z) {
    v[++num] = y;
    w[num] = z;
    nex[num] = first[x];
    first[x] = num;
}
inline void Find_cir(int u, int fa) {
    if (vis[u]) {
        for (int i = top; i >= 1; i--) {
            cir[stu[i]] = true;
            sav[++len[cnt]] = stu[i];
            if (stu[i] == u) break;
        }
        return ;
    }
    stu[++top] = u;
    ver++;
    vis[u] = true;
    for (int i = first[u]; i != -1; i = nex[i]) {
        int to = v[i];
        if ((i ^ fa) != 1 && !cir[to]) {
            edg++;
            Find_cir(to, i);    
        }
    }
    top--;
}
inline void DFS(int u, int fa) {
    for (int i = first[u]; i != -1; i = nex[i]) {
        int to = v[i];
        if (!cir[to] && fa != to) {
            m += (to > n ? -w[i] : w[i]);
            DFS(to, u);
        }
    }
}
inline void dfs(int Rot, int u, int fa) {
    for (int i = first[u]; i != -1; i = nex[i]) {
        int to = v[i];
        if ((fa ^ i) != 1 && cir[to]) {
            val[cnt] += (u > n ? -w[i] : w[i]);
            if (Rot != to) dfs(Rot, to, i);
        }
    }
}
inline void sol() {
    for (int i = 1; i <= len[cnt]; i++) DFS(sav[i], 0);
    for (int i = first[sav[1]]; i != -1; i = nex[i]) {
        int to = v[i];
        if (cir[to]) {
            val[cnt] += (sav[1] > n ? -w[i] * 2 : w[i] * 2);
            dfs(sav[1], to, 0);
            break;
        } 
    }
    m += -val[cnt];
    val[cnt] = 2 * val[cnt];
}
int main() {
    memset(first, -1, sizeof first);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n * 2; i++) {
        int x, y;
        cin >> x >> y >> c[i];
        add(x, y + n, c[i]);
        add(y + n, x, c[i]);
    }
    for (int i = 1; i <= n * 2; i++) {
        if (!vis[i])  {
            ver = 0, edg = 0;
            ++cnt;
            Find_cir(i, 0);
            if (ver != edg) {
                cout << "NO\n";
                return 0;
            }
            sol();
        }
    }
    sort(val + 1, val + cnt + 1);
    int tem = cnt; cnt = 0; 
    val[0] = -2e9;
    for (int i = 1; i <= tem; i++) {
        if (val[i] != val[i - 1]) {
            a[++cnt].val = val[i];
            a[cnt].cnt = 1;
        } else a[cnt].cnt++;
    }
    bas = n * 20;
    dp[bas] = 1;
    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; a[i].cnt; j = min(j * 2, a[i].cnt -= j)) {
            if (a[i].val < 0) dp = (dp | (dp >> (-a[i].val * j)));
            else dp = (dp | (dp << (a[i].val * j)));
        }
    } 
    bool ans = 0;
    for (int i = -k; i <= k; i++) ans |= dp[i + bas - m];
    if (ans) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}