BJOI2011 严格次小生成树 解题报告

【问题描述】  

　　小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。 

　　正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边e的权值) 

　　　　　　　　　 

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

 【输入格式】  

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

 【输出格式】  

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

 【输入样例】   

5 6

1 2 1

1 3 2

2 4 3

3 5 4

3 4 3

4 5 6

 【输出样例】  

11 

 【数据范围】  

数据中无向图无自环； 

50% 的数据N≤2 000 M≤3 000； 

80% 的数据N≤50 000 M≤100 000； 

100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

 【来源】  

BJOI2011

 解题思路：根据题意，要求严格次小生成树可以先求出最小生成树，然后依次枚举非树边，每枚举一条，在所形成的环中找出 比非树边小的最大边，计算出边权和，并取最小值。生成最小生成树需先使用克鲁斯卡尔算法，找出边和所连接的点，然后以任意一点为根进行DFS将树生成出来并计算树上节点的父亲节点、深度、以及到所选根的边权和。在枚举每条非树边，运用LCA，找出非树边连接的两点到最近公共祖先路径上经过的边比非树边小的最大值，然后删去该边，算出边权和，取最小值即为所求。需要注意的是，根据该题的数据范围，输出的答案可能超过int范围。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int maxn=100005;
typedef long long LL;
int N,M,x,y,z;
struct edge{int u,v,w;};
vector<edge>E;  //运用边集数组建立存储结构
vector<int>g[maxn],w[maxn];
int fa[maxn],pa[maxn],dep[maxn];
LL d[maxn];
bool vis[300005];  //用于判断是否为非树边
void initial()
{
	for(int i=1;i<=N;i++)
	pa[i]=i;
}
bool cmp(edge aa,edge bb)
{
	return aa.w<bb.w;
}
int find(int x)
{
	if(pa[x]==x)  return x;
	int root=find(pa[x]);
	pa[x]=root;
	return root;
}
bool check(int x,int y)
{
	if(find(x)==find(y))  return 1;
	return 0;
}
void bing(int x,int y)
{
	pa[find(x)]=find(y);
}
LL kruscal()
{
	initial();
	memset(vis,0,sizeof(vis));
	LL sum=0,cnt=0;
	sort(E.begin(),E.end(),cmp);
	for(int i=0;i<E.size();i++)
	{
		if(!check(E[i].u,E[i].v))
		{
			bing(E[i].u,E[i].v);
			sum+=E[i].w;
			cnt++;
			g[E[i].u].push_back(E[i].v);
			w[E[i].u].push_back(E[i].w);
			g[E[i].v].push_back(E[i].u);
			w[E[i].v].push_back(E[i].w);
			vis[i]=1;
		}
		if(cnt==N-1)  break;
	}
	return sum;
}
void DFS(int i,int f,int de)
{
	fa[i]=f;
	dep[i]=de;
	for(int k=0;k<g[i].size();k++)
	{
		int j=g[i][k],c=w[i][k];
		if(fa[i]==j)  continue;
		d[j]=d[i]+c;
		DFS(j,i,de+1);
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])  swap(x,y);
	while(dep[x]!=dep[y])  x=fa[x];
	while(x!=y)  x=fa[x],y=fa[y];
	return x;
}
int getmax(int x,int y,int c)
{
	int z=LCA(x,y);
	int maxt=-1;
	while(x!=z)
	{
		int tt=(int)d[x]-d[fa[x]];
		if(tt<c) maxt=max(maxt,tt); //求的是严格次小生成树，所以找的是比非树边小的边的最大值
		x=fa[x];
	}
	while(y!=z)
	{
		int tt=(int)d[y]-d[fa[y]];
		if(tt<c) maxt=max(maxt,tt);
		y=fa[y];
	}
	return maxt;
}
int main()
{
	freopen("48.in","r",stdin);
	//freopen("48.txt","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		E.push_back((edge){x,y,z});
	}
	LL sum=kruscal();
	DFS(1,1,1);
	LL ans=100000000000005ll;  //注意long long赋值的写法
	for(int k=0;k<E.size();k++)
	{
		if(vis[k]==1)  continue;  //枚举非树边
		int t=getmax(E[k].u,E[k].v,E[k].w);
		if(t<0)  continue;  //不存在比非树边小的边
		if(E[k].w>t)  ans=min(ans,sum+E[k].w-t);
	}
	cout<<ans<<'\n';
	return 0;
}