bzoj_2042 Will的烦恼

题目:

  大家小时候应该都喜欢自己动手做一些小制作,Will也是这样的。Will还记得他小时候喜欢用色卡纸剪剪贴贴弄出一些看起来很奇怪的东西,而自己却好像做出了件艺术品似的满心的欢喜。说真的,偶尔翻翻自己小时候的东西,想想小时候的事,真是一件非常温馨的事。
  这几天,Will决定重温一下小时候的记忆。色卡纸显然缺乏立体感,于是Will找来了一大摞的彩绳和一些绳环(用来系绳子),准备用这些彩绳和绳环做一个大大的艺术品。
  一共有N个绳环和M根彩绳,方便起见,绳环从1到N分别编号,彩绳则从1到M分别编号。编号为i的彩绳有一个长度Ci和一个美丽程度Di,并且只能连接两个特定的绳环:绳环Xi和绳环Yi。 Will会按照一定的次序将彩绳依次系到绳环上。由于Will希望制作一个大大的艺术品,所以当一条彩绳连接特定的绳环之后,Will会找出所有包含这条彩绳的彩绳圈,然后将每个彩绳圈中长度最短的那条彩绳,从绳环上取下来放到一边。如果有多条最短的彩绳,喜欢新事物的Will会将其中(指那些长度最短的彩绳)最早系到绳环上的那条彩绳取下来。 最后,连在绳环上的彩绳就与绳环一起,组成了一个大大的艺术品咯!
  Will保证,所有绳环最后都会连在一起。 艺术品上所有绳子美丽程度的和,就是这件大大的艺术品的美丽程度。 Will当然希望他的艺术品显得更漂亮些了,所以他希望艺术品的美丽程度能够最大化。 显然,按不同的顺序系彩绳,会制作出不同的艺术品。这里不妨把系彩绳的顺序称为一个制作艺术品的方案,不难发现,一个方案可以简单的用一个1到M的排列来表示。 Will记得,他小时候总是会按照方案的字典序,从字典序最小的方案开始,一个方案接着一个方案的尝试,最后找出能做出最美丽艺术品的方案。
  不过,现在Will长大了,他望着面前一大摞的彩绳,猛然意识到,这回他似乎需要尝试很久很久…… Will需要你的帮助。请你帮Will找出,他将最早尝试的,并且能够做出最美丽艺术品的方案。
  【说明】一个绳环可以系上任意数量的彩绳。 所谓彩绳圈,指的是一个长度不小于2的彩绳编号的序列(A1,A2,…,An),满足任意元素均不相同,且对应存在一个同样长度为n,元素互不相同的绳环编号的序列(B1,B2,…,Bn),满足对于任意整数i∈[1,n),彩绳Ai连接绳环Bi和Bi+1,特别的,彩绳An连接绳环Bn和B1。 对于一个方案P,即一个1到M的排列(P1,P2,…,PM),表示第i个系到绳环上的彩绳,就是编号为Pi的彩绳。 对于两个方案P和Q,如果P的字典序小于Q,则一定存在一个i,使得Pi < Qi。

思路:

  把所有边按照 降序排列,跑最小生成树就能确定哪些边是计入最终答案的(称之为树边)。那么现在的问题就是如何排列边,使得树边不会被非树边替换掉。
  如果已经确定了某条非树边 能替换掉树边 ,那么在最终答案里, 一定在 之前。根据这样的关系可以连出一张拓扑图,只要用堆求出拓扑图的最小遍历即可。因为非树边之间不会存在边,非树边之间肯定是按编号从小到大遍历的,所以某条树边如果会和多个非树边有替换关系,那么只要和编号最大的连边即可。
  根据题意,每条树边只会被与它边权相同的非树边替换。也就是说非树边 能替换的边也就是 路径上所有边权与它相同的边。每次处理边权相同的边,树剖加线段树维护每条边被覆盖的最大编号,这样就能 搞定了。
  据说还有一种 用并查集实现的做法。(不过我没去找)

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 50005, M = 100005;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
Link<M, M * 2, int> DAG;
Link<N, N * 2, int> T;

int ufs[N];
int find(int x) {
    return x == ufs[x] ? x : ufs[x] = find(ufs[x]);
}

struct Edge {
    int c, d, id, u, v;
} edge[M];
bool cmp(Edge a, Edge b) {
    if(a.c != b.c) return a.c > b.c;
    if(a.d != b.d) return a.d > b.d;
    return a.id > b.id;
}

bool mark[M];
void kruskal(int n, int m) {
    rep(i, 1, n) ufs[i] = i;
    sort(edge + 1, edge + 1 + m, cmp);
    rep(i, 1, m) {
        int a = find(edge[i].u), b = find(edge[i].v);
        if(a == b) continue;
        mark[edge[i].id] = true;
        ufs[a] = b;
        T.add(edge[i].u, edge[i].v); T.add(edge[i].v, edge[i].u);
    }
    int las = 0;
    rep(i, 1, m) 
        if(!mark[i]) {
            if(las) DAG.add(las, i);
            las = i;
        }
}

int dep[N], fa[N], sz[N], hs[N], tp[N], dfn[N], cur;
void dfs1(int o, int f) {
    sz[o] = 1; fa[o] = f; dep[o] = dep[f] + 1;
    erep(k, T, o) {
        int v = T[k];
        if(v == f) continue;
        dfs1(v, o);
        sz[o] += sz[v];
        if(sz[v] > sz[hs[o]]) hs[o] = v;
    }
}
void dfs2(int o, int f, int t) {
    tp[o] = t; dfn[o] = ++cur;
    if(hs[o]) dfs2(hs[o], o, t);
    erep(k, T, o) {
        int v = T[k];
        if(v == f || v == hs[o]) continue;
        dfs2(v, o, v);
    }
}

int mx[N << 2], vec[N << 2], tot;
bool inv[N << 2];
#define mid (L + R >> 1)
#define ls (o << 1)
#define rs (o << 1 | 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
void upd(int l, int r, int d, int o, int L, int R) {
    if(l == L && r == R) {
        tomax(mx[o], d); 
        if(tomax(inv[o], true)) vec[++tot] = o;
        return;
    }
    if(r <= mid) upd(l, r, d, lson);
    else if(l > mid) upd(l, r, d, rson);
    else upd(l, mid, d, lson), upd(mid + 1, r, d, rson);
}
int qry(int x, int o, int L, int R) {
    if(L == R) return mx[o];
    if(x <= mid) return max(mx[o], qry(x, lson));
    else return max(mx[o], qry(x, rson));
}

void upd(int u, int v, int d, int n) {
    while(tp[u] != tp[v]) {
        if(dep[fa[tp[u]]] < dep[fa[tp[v]]]) swap(u, v);
        upd(dfn[tp[u]], dfn[u], d, 1, 1, n);
        u = fa[tp[u]];
    }
    if(u == v) return;
    if(dfn[u] > dfn[v]) swap(u, v);
    upd(dfn[u] + 1, dfn[v], d, 1, 1, n);
}

priority_queue<int> hp;
int ind[M];
void output(int m) {
    rep(o, 1, m) 
        erep(k, DAG, o)
            ind[DAG[k]]++;
    rep(o, 1, m) if(!ind[o]) hp.push(-o);
    while(!hp.empty()) {
        int o = -hp.top(); hp.pop();
        printf("%d ", o);
        erep(k, DAG, o) 
            if(--ind[DAG[k]] == 0)
                hp.push(-DAG[k]);
    }
    puts("");
}

int main() {
    // freopen("data.in", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    rep(i, 1, m) {
        int u, v, c, d;
        scanf("%d%d%d%d", &u, &v, &c, &d);
        edge[i] = (Edge) {c, d, i, u, v};
    }
    kruskal(n, m);
    dfs1(1, 0); dfs2(1, 0, 1);
    for(int i = 1, t = 1; i <= m; i = ++t) {
        int tot = 0;
        while(t < m && edge[i].c == edge[t + 1].c) t++;
        rep(k, i, t) if(!mark[edge[k].id]) {
            int a = edge[k].u, b = edge[k].v;
            upd(a, b, edge[k].id, n);
        }
        rep(k, i, t) if(mark[edge[k].id]) {
            int a = edge[k].u, b = edge[k].v;
            if(fa[b] == a) swap(a, b);
            int p = qry(dfn[a], 1, 1, n);
            if(p != 0) DAG.add(p, edge[k].id);
        }
        while(tot) {
            int o = vec[tot--];
            mx[o] = inv[o] = 0;
        }
    }
    output(m);
    return 0;
}