【题解】LOJ 2245 「NOI2014」魔法森林

Problem

给定一个 $n$ 个点 $m$ 条边的图,每条边有两个权值 $a_i,b_i$

求一条 $1-n$ 的路径 $p_1,p_2,\cdots,p_x$, 最小化 $\max \{a_{p_1},a_{p_2},\cdots,a_{p_x}\}+\max \{b_{p_1},b_{p_2},\cdots,b_{p_x}\}$

Thought

双费用最小瓶颈生成树

设某情况中情况中 $A=\max \{a_{p_1},a_{p_2}\cdots,a_{p_x}\},B=\max \{b_{p_1},b_{p_2},\cdots,b_{p_x}\}$
在 $A$ 单调递增时,$B$ 一定是单调不增的

考虑用 $LCT$ 维护图,每次按照 $a$ 从小到大加边,然后对于成环的部分直接去掉 $b$ 最大的,那么答案就是 $1-n$ 路径上的最大值 + $A$

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 50010;
const int M = 100010;

#define L (ch[x][0])
#define R (ch[x][1])

struct LCT {
    int rt[N + M], fa[N + M], ch[N + M][2];
    int sta[N + M], top;
    int key[N + M];
    int maxKey[N + M];
    bool rev[N + M];
    bool get(int x) {
        return ch[fa[x]][1] == x;
    }
    bool isr(int x) {
        return !(ch[fa[x]][0] == x || ch[fa[x]][1] == x);
    }
    void upd(int x) {
        maxKey[x] = x;
        if(L) maxKey[x] = (key[maxKey[L]] > key[maxKey[x]] ? maxKey[L] : maxKey[x]);
        if(R) maxKey[x] = (key[maxKey[R]] > key[maxKey[x]] ? maxKey[R] : maxKey[x]);
    }
    void pus(int x) {
        if(rev[x]) {
            swap(L, R);
            if(L) rev[L] ^= 1;
            if(R) rev[R] ^= 1;
        }
        rev[x] = 0;
    }
    void rotate(int x) {
        int old = fa[x], oldf = fa[old], w = get(x);
        if(!isr(old)) ch[oldf][ch[oldf][1] == old] = x;
        ch[old][w] = ch[x][w ^ 1]; fa[ch[old][w]] = old;
        ch[x][w ^ 1] = old; fa[old] = x;
        fa[x] = oldf;
        upd(old); upd(x);
    }
    void splay(int x) {
        sta[++ top] = x;
        for(int i = x; !isr(i); i = fa[i])
            sta[++ top] = fa[i];
        while(top)
            pus(sta[top --]);
        for(int f; !isr(x); rotate(x))
            if(!isr(f = fa[x]))
                rotate(get(x) == get(f) ? f : x);
    }
    void access(int x) {
        for(int i = 0; x; i = x, x = fa[x]) {
            splay(x);
            ch[x][1] = i;
            upd(x);
        }
    }
    void makeroot(int x) {
        access(x);
        splay(x);
        rev[x] ^= 1;
    }
    void split(int x, int y) {
        makeroot(x);
        access(y);
        splay(y);
    }
    int query(int x, int y) {
        split(x, y);
        return maxKey[y];
    }
    int find(int x) {
        access(x);
        splay(x);
        while(L) x = L;
        return x;
    }
    
    void link(int x, int y) {
        makeroot(x);
        fa[x] = y;
    }
    void cut(int x, int y) {
        split(x, y);
        ch[y][0] = 0;
        fa[x] = 0;
    }
}lct;

int n, m;
struct Edge {
    int x, y, a#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
int n, m, T[N];
char Opt[N][4];
void solve(bool &one, bool &zero, int bin, char str, int t) {
    bool x = t & (1 << bin);
    if(str == 'O') {
        one |= x;
        zero |= x;
    }
    else if(str == 'X') {
        one ^= x;
        zero ^= x;
    }
    else if(str == 'A') {
        one &= x;
        zero &= x;
    }
}
int main() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i) {
        scanf("%s", Opt[i]);
        scanf("%d", &T[i]);
    }
    int now = 0, ans = 0;
    for(int i = 30; i >= 0; -- i) {
        bool One = 1, Zero = 0;
        for(int j = 1; j <= n; ++ j)
            solve(One, Zero, i, Opt[j][0], T[j]);
        if(now + (1 << i) > m)
            ans += (Zero << i);
        else {
            if(Zero >= One)
                ans += (Zero << i);
            else {
                ans += (One << i);
                now += (1 << i);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}, b;
    bool operator < (const Edge E) const {
        if(a == E.a)
            return b < E.b;
        return a < E.a;
    }
}e[M];

int main() {
    n = read(); m = read();
    for(int i = 1; i <= m; ++ i) {
        e[i].x = read();
        e[i].y = read();
        e[i].a = read();
        e[i].b = read();
    }
    sort(e + 1, e + m + 1);
    int ans = INT_MAX, flag = 0;
    for(int i = 1; i <= m; ++ i) {
        if(e[i].x == e[i].y) continue;
        lct.key[i + n] = e[i].b;
        if(lct.find(e[i].x) != lct.find(e[i].y)) {
            lct.link(e[i].x, i + n);
            lct.link(e[i].y, i + n);
        }
        else {
            int edg = lct.query(e[i].x, e[i].y);
            if(e[edg - n].b > e[i].b) {
                lct.cut(e[edg - n].x, edg);
                lct.cut(e[edg - n].y, edg);
                lct.link(e[i].x, i + n);
                lct.link(e[i].y, i + n);
            }
        }
        if(!flag && lct.find(1) == lct.find(n))
            flag = 1;
        if(flag)
            ans = min(ans, e[i].a + e[lct.query(1, n) - n].b);
    }
    printf("%d\n", ans == INT_MAX ? - 1 : ans);
    return 0;
}
Comments

添加新评论