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 + ;
int first[maxn], num;
struct Edge {
int u, v, w, id, tonext;
}e[maxn * ];
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[][] = {"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] = ;
}
} else low[cur] = min(low[cur], DFN[v]);
}
}
void work() {
num = ;
memset(first, -, sizeof first);
for (int i = ; i <= maxn - ; ++i) fa[i] = i;
int n, m;
cin >> n >> m;
for (int i = ; i <= m; ++i) {
cin >> data[i].u >> data[i].v >> data[i].w;
data[i].id = i;
}
sort(data + , data + + m, cmp1);
for (int i = ; i <= m;) {
int en;
for (en = i + ; 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] = ;
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), -);
}
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] = -;
DFN[x] = DFN[y] = low[x] = low[y] = false;
when = ;
}
}
i = en;
}
for (int i = ; 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 ;
}