Description
You are given a connected weighted undirected graph without any loops and multiple edges.
Let us remind you that a graph's spanning tree is defined as an acyclic connected subgraph of the given graph that includes all of the graph's vertexes. The weight of a tree is defined as the sum of weights of the edges that the given tree contains. The minimum spanning tree (MST) of a graph is defined as the graph's spanning tree having the minimum possible weight. For any connected graph obviously exists the minimum spanning tree, but in the general case, a graph's minimum spanning tree is not unique.
Your task is to determine the following for each edge of the given graph: whether it is either included in any MST, or included at least in one MST, or not included in any MST.
给一个带权的无向图，保证没有自环和重边。 由于最小生成树不唯一，因此你需要确定每一条边是以下三种情况哪一个
1.一定在所有 MST 上。
2.可能在某个 MST 上。
3.一定不可能在任何 MST 上。
Solution
先考虑次小生成树的做法。我们先随便求出一棵最小生成树，那么对于那些非树边 \((x,y)\) 来说，能被替换进最小生成树，当前仅当权值等于当前最小生成树上 \(x\) 到 \(y\) 的路径上的最大值（因为不可能小于）。那这样的话我们求可以求出非树边的答案了。
而怎么判断树边是否可以被替换呢？考虑对于每个树边，记录可替换该树边的最小边权。当最小边权等于树边的边权时，就表示该树边是可被替换的。记录的方法可以用树剖加上线段树，在枚举非树边时更新对应路径上每条边的最小可被替换值，用线段树维护区间取 \(\min\)。但由于查询是单点查询，因此使用基本的线段树就可以做到。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,tot,cnt,f[N],w[N],siz[N],son[N],dfn[N],rk[N],tp[N],dep[N],trmn[N<<2],trmx[N<<2],lzmn[N<<2],ans[N];
bool bj[N];
struct Edge{int x,y,z,id;}e[N];
struct node {int to,next,head,val;}a[N<<1];
void add(int x,int y,int z)
{
a[++tot].to=y;a[tot].val=z;a[tot].next=a[x].head;a[x].head=tot;
a[++tot].to=x;a[tot].val=z;a[tot].next=a[y].head;a[y].head=tot;
}
bool cmp(Edge x,Edge y) {return x.z<y.z;}
int find(int x)
{
if (f[x]!=x) f[x]=find(f[x]);
return f[x];
}
void to_point(int x,int fa)
{
for (int i=a[x].head;i;i=a[i].next)
{
int y=a[i].to,z=a[i].val;
if (y==fa) continue;
w[y]=z;
to_point(y,x);
}
}
void dfs1(int x,int fa)
{
siz[x]=1;f[x]=fa;dep[x]=dep[fa]+1;
for (int i=a[x].head;i;i=a[i].next)
{
int y=a[i].to;
if (y==fa) continue;
dfs1(y,x);
if (siz[y]>siz[son[x]]) son[x]=y;
siz[x]+=siz[y];
}
}
void dfs2(int x,int top)
{
dfn[x]=++cnt;rk[cnt]=x;tp[x]=top;
if (son[x]) dfs2(son[x],top);
for (int i=a[x].head;i;i=a[i].next)
{
int y=a[i].to;
if (y==f[x]||y==son[x]) continue;
dfs2(y,y);
}
}
void build(int x,int l,int r)
{
trmn[x]=inf;lzmn[x]=-1;
if (l==r) {trmx[x]=w[rk[l]];return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
trmx[x]=max(trmx[x<<1],trmx[x<<1|1]);
}
void pushdown(int x)
{
if (lzmn[x]!=-1)
{
trmn[x<<1]=min(trmn[x<<1],lzmn[x]);
if (lzmn[x<<1]==-1) lzmn[x<<1]=lzmn[x];
else lzmn[x<<1]=min(lzmn[x<<1],lzmn[x]);
trmn[x<<1|1]=min(trmn[x<<1|1],lzmn[x]);
if (lzmn[x<<1|1]==-1) lzmn[x<<1|1]=lzmn[x];
else lzmn[x<<1|1]=min(lzmn[x<<1|1],lzmn[x]);
lzmn[x]=-1;
}
}
int query(int x,int l,int r,int p,int q)
{
if (p>q) return 0;
if (l>=p&&r<=q) return trmx[x];
int mid=(l+r)>>1,res=0;
if (p<=mid) res=max(res,query(x<<1,l,mid,p,q));
if (q>mid) res=max(res,query(x<<1|1,mid+1,r,p,q));
return res;
}
void modify(int x,int l,int r,int p,int q,int v)
{
if (p>q) return;
if (l>=p&&r<=q)
{
trmn[x]=min(trmn[x],v);
if (lzmn[x]==-1) lzmn[x]=v;
else lzmn[x]=min(lzmn[x],v);
return;
}
pushdown(x);
int mid=(l+r)>>1;
if (p<=mid) modify(x<<1,l,mid,p,q,v);
if (q>mid) modify(x<<1|1,mid+1,r,p,q,v);
trmn[x]=min(trmn[x<<1],trmn[x<<1|1]);
}
int querymn(int x,int l,int r,int p)
{
if (l==r) return trmn[x];
pushdown(x);
int mid=(l+r)>>1;
if (p<=mid) return querymn(x<<1,l,mid,p);
else return querymn(x<<1|1,mid+1,r,p);
}
int query_max(int x,int y)
{
int res=0;
while (tp[x]!=tp[y])
{
if (dep[tp[x]]<dep[tp[y]]) swap(x,y);
res=max(res,query(1,1,n,dfn[tp[x]],dfn[x]));
x=f[tp[x]];
}
if (dep[x]>dep[y]) swap(x,y);
res=max(res,query(1,1,n,dfn[x]+1,dfn[y]));
return res;
}
void modify_min(int x,int y,int v)
{
while (tp[x]!=tp[y])
{
if (dep[tp[x]]<dep[tp[y]]) swap(x,y);
modify(1,1,n,dfn[tp[x]],dfn[x],v);
x=f[tp[x]];
}
if (dep[x]>dep[y]) swap(x,y);
modify(1,1,n,dfn[x]+1,dfn[y],v);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[i].x=x;e[i].y=y;e[i].z=z;e[i].id=i;
}
for (int i=1;i<=n;++i)
f[i]=i;
sort(e+1,e+m+1,cmp);
for (int i=1;i<=m;++i)
{
int x=find(e[i].x),y=find(e[i].y);
if (x!=y)
{
f[y]=x;
add(e[i].x,e[i].y,e[i].z);
bj[i]=true;
}
}
memset(f,0,sizeof(f));
to_point(1,0);
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for (int i=1;i<=m;++i)
{
if (bj[i]) continue;
int res=query_max(e[i].x,e[i].y);
modify_min(e[i].x,e[i].y,e[i].z);
if (res==e[i].z) ans[e[i].id]=2;
else ans[e[i].id]=0;
}
for (int i=1;i<=m;++i)
{
if (!bj[i]) continue;
int res;
if (dep[e[i].x]>dep[e[i].y]) res=querymn(1,1,n,dfn[e[i].x]);
else res=querymn(1,1,n,dfn[e[i].y]);
if (res==e[i].z) ans[e[i].id]=2;
else ans[e[i].id]=1;
}
for (int i=1;i<=m;++i)
{
if (ans[i]==0) printf("none\n");
if (ans[i]==1) printf("any\n");
if (ans[i]==2) printf("at least one\n");
}
return 0;
}