佛山网站建设是哪个好,设计制作小车的基本步骤,建设银行如何招聘网站,外包网站多少钱澪有个 n n n 个点 m m m 条边的无向图#xff0c;每条边都有蓝白两种颜色中的一种#xff0c;保证蓝色的边形成了这个图的一个生成树。
她希望给这些边赋上边权#xff0c;保证边权是 1 ∼ m 1 \sim m 1∼m 的排列#xff0c;使得蓝色的边是最小生成树。
希望这些边权…澪有个 n n n 个点 m m m 条边的无向图每条边都有蓝白两种颜色中的一种保证蓝色的边形成了这个图的一个生成树。
她希望给这些边赋上边权保证边权是 1 ∼ m 1 \sim m 1∼m 的排列使得蓝色的边是最小生成树。
希望这些边权形成的序列字典序最小也就是先比较第一条边的边权再比较第二条边的边权依次类推。 n , m ≤ 5 × 1 0 5 n,m\le5\times10^5 n,m≤5×105 对于一个生成树是最小生成树都有任意的非树边的边权都与其形成环的树边的边权大。
一种想法是考虑按输入顺序贪心确定每条边权值对于一条非树边记 k k k 为与之形成环的未被确定权值的树边数量给这 k k k 条边按顺序确定权值再给这条非树边设权值对于树边直接赋权值即可。正确性显然
这样做时间复杂度是 O ( n m ) O(nm) O(nm)考虑优化。注意到每次操作时被标记的树边是连续的所以可以用并查集维护这个连通块深度最小的点每次像树剖找 LCA 选最深的点往上跳到所在连通块的顶端直到两个点属于一个连通块为止。由于用了并查集维护每条边只会走一次后面又排序时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。
具体实现看代码
#includebits/stdc.h
using namespace std;
const int N5e51;
int n,m,f[N],val[N],p[N],ans[N],cnt1;
int head[N],nxt[N1],to[N1],w[N1],cnt;
int dep[N],fa[N],sz[N],son[N],top[N];
struct node
{int u,v,id,type;
}a[N];
void add(int u,int v,int W)
{to[cnt]v;w[cnt]W;nxt[cnt]head[u];head[u]cnt;
}
void dfs(int u,int f)
{fa[u]f;dep[u]dep[f]1;for(int ihead[u];i;inxt[i]){if(to[i]!f){val[to[i]]w[i];dfs(to[i],u);}}
}
int find(int x)
{return xf[x]?x:f[x]find(f[x]);
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d%d,a[i].u,a[i].v,a[i].type);if(a[i].type) add(a[i].u,a[i].v,i),add(a[i].v,a[i].u,i);}for(int i1;in;i) f[i]i;dfs(1,0);for(int i1;im;i){int xa[i].u,ya[i].v,cnt0;while(find(x)!find(y)){if(dep[find(x)]dep[find(y)]) swap(x,y);xfind(x);f[x]find(fa[x]);p[cnt]val[x];}sort(p1,p1cnt);for(int j1;jcnt;j) ans[p[j]]cnt1;if(a[i].type0) ans[i]cnt1;}for(int i1;im;i) printf(%d ,ans[i]);
}
