External link:

https://www.facebook.com/hackercup/problems.php?pid=182208915220500&round=222291111185610
http://codeforces.com/gym/100159

Problem A. Monopoly

Brief description:

.. 给定 n 个结点。。让你按照给定的顺序合并 n-1 次变成一颗树。。由你决定每次合并时。谁作为父亲。。。
。。使得每个结点的孩子不超过 M 个。。。并且高度最小。。

Analysis:

… 用并查集模拟即可。。每次合并的时候维护所有的合法方案即可。。
（。。即开一个 vector 。。(高度, 宽度）。。高度递增。。宽度递减。。。

//}/* .................................................................................................................................. */

const int N = 32768;

namespace dsu{
    int p[N]; VII c[N];
    int n, m;

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

    void Union(int x, int y){
        x = Find(x), y = Find(y); VII cc;
        int h = c[y][0].fi+1; ECH(it, c[x]) if (it->se<m) cc.PB(MP(max(it->fi, h), it->se+1));
        h = c[x][0].fi+1; ECH(it, c[y]) if (it->se<m) cc.PB(MP(max(it->fi, h), it->se+1));
        SRT(cc), p[y] = x; CLR(c[x]); ECH(it, cc) if (c[x].empty() || it->se < c[x].back().se) c[x].PB(*it);
    }

    void gao(){
        DO(n-1) Union(RD(), RD());
    }

    void init(){
        RD(n, m); REP_1(i, n) p[i] = i, CLR(c[i]), c[i].PB(MP(1, 0));
    }
} using namespace dsu;


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        init(), gao();
        OT(c[Find(1)].front().fi);
    }
}

Problem B. Road Removal

Brief description:

.无向图。。n 个结点 m 条边。。前 k 个结点是关键结点。。
。。要求删除最少数据的边使得环不会 involve 关键结点。。。

Analysis:

…。。居然还是并查集。。（？。。
先把所有安全边全部用上。。（不与关键点相关的边。。
。。。再看非安全边能不能合并即可。。。

//}/* .................................................................................................................................. */

const int N = int(1e4) + 9, M = int(5e4) + 9;

namespace dsu{
    int p[N], r[N], n, m, k, res;
    int a[M], b[M];

    void Make(int x){
        r[x] = 0, p[x] = x;
    }

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

    bool Union(int x, int y){
        x = Find(x), y = Find(y);
        if (x == y) return false;
        if (r[x] < r[y]) p[x] = y;
        else {
            if (r[x] == r[y]) ++r[x];
            p[y] = x;
        }
        return true;
    }

    void gao(){
        REP(i, m){
            RD(a[i], b[i]); if (a[i] >= k && b[i] >= k) Union(a[i], b[i]);
            else ++res;
        }

        REP(i, m) res -= Union(a[i], b[i]);
    }

    void init(){
        RD(n, m, k); REP(i, n) Make(i);
        res = 0;
    }
} using namespace dsu;


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        init(); gao();
        OT(res);
    }
}

Posted by xiaodao
Category: Facebook Hacker Cup