D. Edges in MST 图论

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

base on 克鲁斯卡尔，

首先每次都是对权值相同的边进行统一处理，假如加入了当前这条边出现了回路，那就能确定这条边是none的。

否则，让它加入进图，（先不合并），然后找到这个图的桥，那些就是any的，其他都是at least one的。

唯一要注意的就是不能像克鲁斯卡尔这样，没加入一条边，都合并。这里是把权值相同的边加入来后，再统一合并。

4 4
1 2 1
2 3 1
3 4 2
1 3 2

any
any
any
none

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 1e5 + 20;
int first[maxn], num;
struct Edge {
    int u, v, w, id, tonext;
}e[maxn * 2];
void addEdge(int u, int v, int w, int id) {
    e[num].u = u, e[num].v = v, e[num].w = w, e[num].id = id, e[num].tonext = first[u];
    first[u] = num++;
}
struct Node {
    int u, v, w, id;
}data[maxn];
bool cmp1(struct Node a, struct Node b) {
    return a.w < b.w;
}
int fa[maxn];
int tofind(int x) {
    if (fa[x] == x) return x;
    else return fa[x] = tofind(fa[x]);
}
char ans[][20] = {"none", "any", "at least one"};
int res[maxn], in[maxn];
int DFN[maxn], low[maxn], when, vis[maxn];
void dfs(int cur, int fromID) {
    DFN[cur] = low[cur] = ++when;
    for (int i = first[cur]; ~i; i = e[i].tonext) {
        int v = e[i].v;
        if (e[i].id == fromID) continue;
        vis[e[i].id] = true;
        if (!DFN[v]) {
            dfs(v, e[i].id);
            low[cur] = min(low[cur], low[v]);
            if (low[v] > DFN[cur]) {
                res[e[i].id] = 1;
            }
        } else low[cur] = min(low[cur], DFN[v]);
    }
}
void work() {
    num = 0;
    memset(first, -1, sizeof first);
    for (int i = 1; i <= maxn - 20; ++i) fa[i] = i;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> data[i].u >> data[i].v >> data[i].w;
        data[i].id = i;
    }
    sort(data + 1, data + 1 + m, cmp1);
    for (int i = 1; i <= m;) {
        int en;
        for (en = i + 1; en <= m && data[en].w == data[i].w; ++en);
        for (int j = i; j < en; ++j) {
            int x = tofind(data[j].u), y = tofind(data[j].v);
            if (x == y) continue;
            addEdge(x, y, data[j].w, data[j].id);
            addEdge(y, x, data[j].w, data[j].id);
            res[data[j].id] = 2;
            in[data[j].id] = true;
        }
        for (int j = i; j < en; ++j) {
            if (vis[data[j].id] || !in[data[j].id]) continue;
            vis[data[j].id] = true;
            dfs(tofind(data[j].u), -1);
        }
        for (int j = i; j < en; ++j) {
            int x = tofind(data[j].u), y = tofind(data[j].v);
            if (x != y) {
                fa[y] = x;
                first[x] = first[y] = -1;
                DFN[x] = DFN[y] = low[x] = low[y] = false;
                when = 0;
            }
        }
        i = en;
    }
    for (int i = 1; i <= m; ++i) {
        cout << ans[res[i]] << endl;
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    IOS;
    work();
    return 0;
}

View Code

D. Edges in MST 图论

相关推荐