新城建站,上海市网站建,网站建设服务协议书,h5与wordpress正题 题目大意
n个点的一棵树#xff0c;增加了m条密道。对于树上每条边(A,B)(A,B)(A,B)被破坏后#xff0c;要求A∼BA\sim BA∼B经过密道最短。 解题思路 引理:对于每个道路被破坏#xff0c;最多只会经过一条边。 证明:对于每个答案#xff0c;被破坏后#xff0c;所在…正题 题目大意
n个点的一棵树增加了m条密道。对于树上每条边(A,B)(A,B)(A,B)被破坏后要求A∼BA\sim BA∼B经过密道最短。 解题思路 引理:对于每个道路被破坏最多只会经过一条边。 证明:对于每个答案被破坏后所在层数低的点找到一条可以走出他的子树的边就好了如果要走两条边中间的点要不在子树中要不在子树外。在子树中直接那个点走就好了在子树外就不用再走了。 证毕 所以我们就只需要找那一条密道就好了我们考虑用并查集先将密道长度排好然后在每一条密道(x,y,w)(x,y,w)(x,y,w)就看一下xxx和yyy之前有没有合并如果有就直接用那个答案如果没有就合并用新的答案。 code
#includecstdio
#includealgorithm
#includecstring
#define N 100010
using namespace std;
struct node{int to,id,next;
}a[N*2];
struct line{int x,y,w;
}e[N];
int ls[N],tot,x,y,w,ans,dep[N],father[N];
int n,m,S,dfn[N],end[N],cnt,p[N],f[N],d[N];
void addl(int x,int y,int w)//加边
{a[tot].toy;a[tot].idw;a[tot].nextls[x];ls[x]tot;
}
bool cmp(line x,line y)
{return x.wy.w;}
void dfs(int x,int fa)//求深度和父节点以及每个点对应来的编号
{father[x]fa;dep[x]dep[fa]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa) continue;p[y]a[i].id;dfs(y,x);}
}
int gf(int x)//查找
{return f[x]?f[x]gf(f[x]):x;}
void doit(int x,int y)//合并
{d[p[x]]y;f[x]gf(father[x]);xf[x];}
int main()
{scanf(%d%d,n,m);memset(d,-1,sizeof(d));for(int i1;in;i){scanf(%d%d,x,y);addl(x,y,i);addl(y,x,i);}for(int i1;im;i)scanf(%d%d%d,e[i].x,e[i].y,e[i].w);dfs(1,0);sort(e1,em1,cmp);//排序for(int i1;im;i){int ugf(e[i].x),vgf(e[i].y);while(u!v) doit(dep[u]dep[v]?u:v,e[i].w);//将所有的点都get}for(int i1;in;i)printf(%d\n,d[i]);//输出答案
}
