[BJWC2010]严格次小生成树

题目描述

小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边e的权值) \sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)∑e∈EMvalue(e)<∑e∈ESvalue(e)

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

输入输出格式

输入格式：

第一行包含两个整数N 和M，表示无向图的点数与边数。接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

输出格式：

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

输入输出样例

输入样例#1：

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

输出样例#1：

说明

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

最开始没有看懂题目，推不出样例很懵逼，以为要满足每条边都比最小生成树小，后来才知道就是第二小的生成树就可以了...

最开始想到跑完最小生成树之后，对于每条非生成树上的边，求出两个端点路径上的最大值，突然发现好像会出现等于的情况，一脸懵逼。然后只会暴力跳，居然70？？？数据好水啊

最后看题解发现求出次小值即可，这种思路都想不到我真的是太菜了。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define lll long long

using namespace std;

lll read()

{

	lll x=0,w=1;char ch=getchar();

	while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return x*w;

}

const lll N=100010;

lll n,m,cnt,ans,sum=2000000000;

lll fa[N],deep[N],head[N],l[N][20],m1[N][20],m2[N][20],vis[3*N],quan[N];

struct node{

	lll x,y,v;

}f[3*N];

struct Node{

	lll to,next,v;

}edge[2*N];

bool cmp(node p,node q) {return p.v<q.v;}

lll gfa(lll x){if(fa[x]==x)return x;return fa[x]=gfa(fa[x]);}

void add(lll x,lll y,lll z)

{

	cnt++;edge[cnt].to=y;edge[cnt].next=head[x];edge[cnt].v=z;head[x]=cnt;

}

void kruscal()

{

	lll qwe=0;sort(f+1,f+1+m,cmp);

	for(lll i=1;i<=m;i++)

	{

		lll xx=gfa(f[i].x),yy=gfa(f[i].y);

		if(xx!=yy) fa[xx]=yy,qwe++,ans+=f[i].v,add(f[i].x,f[i].y,f[i].v),add(f[i].y,f[i].x,f[i].v),vis[i]=1;

		if(qwe==n-1) break;

	}

}

void dfs(lll k)

{

	for(lll i=head[k];i;i=edge[i].next)

	{

		lll v=edge[i].to;if(deep[v]) continue;

		deep[v]=deep[k]+1;l[v][0]=k;m1[v][0]=edge[i].v;dfs(v);

	}

}

void init()

{

	for(lll i=1;i<=19;i++)

	for(lll j=1;j<=n;j++)

	{

		l[j][i]=l[l[j][i-1]][i-1];

		if(m1[j][i-1]<m1[l[j][i-1]][i-1])

			m1[j][i]=m1[l[j][i-1]][i-1],m2[j][i]=max(m1[j][i-1],m2[l[j][i-1]][i-1]);

		else if(m1[j][i-1]>m1[l[j][i-1]][i-1])

			m1[j][i]=m1[j][i-1],m2[j][i]=max(m1[l[j][i-1]][i-1],m2[j][i-1]);

		else

			m1[j][i]=m1[j][i-1],m2[j][i]=max(m2[l[j][i-1]][i-1],m2[j][i-1]);

	}

}

void changex(lll x,lll i,lll &qwe1,lll &qwe2)

{

	if(qwe1<m1[x][i]) qwe2=max(qwe1,m2[x][i]),qwe1=m1[x][i];

	else qwe2=max(qwe2,m1[x][i]);

}

void changey(lll y,lll i,lll &qwe1,lll &qwe2)

{

	if(qwe1<m1[y][i]) qwe2=max(qwe1,m2[y][i]),qwe1=m1[y][i];

	else qwe2=max(qwe2,m1[y][i]);

}

lll lca(lll x,lll y,lll v)

{

	lll qwe1=0,qwe2=0;if(deep[x]<deep[y]) swap(x,y);

	for(lll i=19;i>=0;i--)

		if(deep[l[x][i]]>=deep[y])

		{

			changex(x,i,qwe1,qwe2);

			x=l[x][i];

		}

	if(x==y) {if(qwe1==v)return qwe2;return qwe1;}

	for(lll i=19;i>=0;i--)

		if(l[x][i]!=l[y][i])

		{

			changex(x,i,qwe1,qwe2);changey(y,i,qwe1,qwe2);

			x=l[x][i];y=l[y][i];

		}

	changex(x,0,qwe1,qwe2);changey(y,0,qwe1,qwe2);

	if(qwe1==v)return qwe2;return qwe1;

}

int main()

{

	n=read();m=read();

	for(lll i=1;i<=n;i++) fa[i]=i;

	for(lll i=1;i<=m;i++)

	{

		f[i].x=read();f[i].y=read();f[i].v=read();

	}

	kruscal();deep[1]=1;dfs(1);init();

	for(lll i=1;i<=m;i++)

	{

		if(vis[i]) continue;

		sum=min(sum,f[i].v-lca(f[i].x,f[i].y,f[i].v));

	}

	cout<<ans+sum;

}

巴特西

[BJWC2010]严格次小生成树（LCA，最小生成树）

[BJWC2010]严格次小生成树

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章