生成树大挑战

Posted on | In

https://codeforces.com/contest/160/problem/D

众所周知连通图的mst可能有多个，现给定一个无向图（n、m<=1e5），要求判断每条边，是存在于所有的mst中，还是至少存在于一个mst中，还是不存在于任一mst中。

我们现在来考虑Kruskal的算法流程，首先对于边按权值排序，从小到大挨个添加（当两个端点不连通时）。当我们遇到若干条权值相同的边，且都满足添加条件时，则可以任选一条，这就是1、2的情况。而如果当前边的两端已经在同一点集中，这条边则不可能被添加，是第三种情况。接下来我们考虑如何区分前两种情况。

首先对于若干条相等的边，如果判断它可以连，就先把对应点集的祖先连接在一起，点集暂时不合并。就这样处理完之后，我们在当前图找桥，复杂度O（刚添加的边数）。桥边属于必选，剩下的边则是可选。然后第三步，则是把这些边两端的点集都合并起来，并把之前的连边信息清空，因为他们现在属于一个点集了，有公共的祖先，就不需要这些内部边了。这里所用到的一个技巧就是，用每个点集的祖先代表这个点集中的所有点，如果一个点集向另一个点集发出两条边，则相当于这两个祖先点连了两条重边，则这两条边都是可选；如果只有一条，那么就必须选择。然后这里的找桥算法也需要修改，为了支持重边的情况，之前算法中是不采用来自父亲的边，现在修改为不采用通向当前点u的这条边，其余通向父亲的重边是可以采用的。这样一来就不会误判桥了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+4;

struct d{
    int u,v,w,pos;
    friend bool operator<(d x,d y){
        return x.w<y.w;
    }
}ds[maxn];

struct edge{
    int to,next;
    int pos;
}es[maxn<<1];
int head[maxn],cnt;
inline void add(int u,int v,int pos){
    es[++cnt]=(edge){ v,head[u],pos};
    head[u]=cnt;
}

int fa[maxn];
int find(int x){
    return (fa[x]==x?x:fa[x]=find(fa[x]));
}

int ans[maxn];
int dfn[maxn],low[maxn],dcnt;
void tarjan(int u,int from){
    //这里from是边的编号(正反边是用同一个编号)，否则多排除掉一些重边（有的话）
    dfn[u]=low[u]=++dcnt;
    for(int i=head[u];i;i=es[i].next){
        int v=es[i].to;
        if(!dfn[v]){
            tarjan(v,es[i].pos);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
                ans[es[i].pos]=2;
            }
        }else if(from!=es[i].pos){
            low[u]=min(low[u],dfn[v]);
        }
    }
}
void merge(int a,int b){
    int A=find(a),B=find(b);
    if(A!=B){
        head[a]=head[b]=head[A]=head[B]=0;
        dfn[a]=dfn[b]=dfn[A]=dfn[B]=0;
        low[a]=dfn[b]=dfn[A]=dfn[B]=0;
        fa[A]=B;
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    memset(head,0,sizeof(int)*(n+1));
    for(int i=1;i<=m;i++){
        cin>>ds[i].u>>ds[i].v>>ds[i].w;
        ds[i].pos=i;
    }
    for(int i=1;i<=n;i++)
        fa[i]=i;
    sort(ds+1,ds+1+m);
    for(int i=1;i<=m;i++){
        int ss=i,ee=i;
        while(ee<m&&ds[ee+1].w==ds[ss].w)
            ee++;
        for(int j=ss;j<=ee;j++){
            int fu=find(ds[j].u);
            int fv=find(ds[j].v);
            if(fu!=fv){
                ans[ds[j].pos]=1;
                add(fu,fv,ds[j].pos);
                add(fv,fu,ds[j].pos);
            }
        }
        for(int j=ss;j<=ee;j++){
            int fu=find(ds[j].u);
            int fv=find(ds[j].v);
            if(!dfn[fu]&&fu!=fv)
                tarjan(fu,-1);
            if(!dfn[fv]&&fu!=fv)
                tarjan(fv,-1);
        }
        for(int j=ss;j<=ee;j++){
            merge(find(ds[j].u),find(ds[j].v));
        }
        i=ee;
    }
    for(int i=1;i<=m;i++){
        switch(ans[i]){
            case 0:
                cout<<"none"<<endl;
                break;
            case 1:
                cout<<"at least one"<<endl;
                break;
            case 2:
                cout<<"any"<<endl;
                break;
        }
    }
}