HDU 5624 KK's Reconstruction 最小生成树

题意:这是bc round 71 div 1 的 1004 直接去看中文题意

分析:

首先,一种合法方案对应了原图的一棵生成树。

我们知道,最小生成树有一个性质是最大边最小。

因此,我们可以枚举生成树的最小边,去掉比该边小的边后对新图求最小生成树,那么我们所要的最优解一定包含在其中。

时间复杂度O(Mlog M+M^2*a (N),显然仅仅这个效率是不够的。

可以发现我们每次枚举后都重新求了最小生成树,事实上这是不必要的。

考虑从大到小枚举生成树的最小边,我们要做的实际上是每次加入一条边,维护当前图的最小生成树。

加入一条边时,我们需要判断这条边能否与之前的边构成环。

I 若能构成环,用该边替代环中最大边一定更优;

II 若不能构成环,直接加入该边即可。

找环中最大边可以用DFS 实现。若图中现有的边数为N-1N−1,我们就可以更新答案。

这样,事件复杂度就降到了O(M\log M+MN)O(MlogM+MN)。

更高的效率的方法,我们涉及的操作为加边、删边、查询路径最大边,因此可以使用LCT 来维护。

注:我按照题解写了一发,肯定是我手残,没有理解人家的意思,我发现我写出来还没题解上的效率不行的快

肯定我不行,

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=;
const int mod=1e9+;
const LL INF=INT_MAX;
int head[maxn],p;
struct Edge
{
LL u,v,next;
LL w,mark;
bool operator<(const Edge &e)const
{
return w<e.w;
}
} edge[],o[];
void add(int u,int v,int w)
{
edge[p].u=u;
edge[p].v=v;
edge[p].w=w;
edge[p].mark=;
edge[p].next=head[u];
head[u]=p++;
}
int fa[maxn];
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
LL tmp,vv,_max;
void dfs(int u,int f,int res)
{
if(u==vv)
tmp=res;
for(int i=head[u]; ~i; i=edge[i].next)
{
if(edge[i].v==f)continue;
if(edge[i].mark)continue;
_max=max(_max,edge[i].w);
int c=res;
if(res==-||edge[i].w>edge[c].w)c=i;
dfs(edge[i].v,u,c);
}
}
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=; i<=m; ++i)
scanf("%I64d%I64d%I64d",&o[i].u,&o[i].v,&o[i].w);
sort(o+,o++m);
for(int i=; i<=n; ++i)fa[i]=i;
p=;
memset(head,-,sizeof(head));
int cnt=;
LL ans=INF;
for(int i=m; i>; --i)
{
tmp=-,_max=,vv=o[i].v;
if(cnt==n-)
{
dfs(o[i].u,,-);
ans=min(ans,_max-o[i+].w);
}
int fx=find(o[i].u);
int fy=find(o[i].v);
if(fx!=fy)
{
++cnt;
fa[fx]=fy;
}
else
{
if(tmp==-)
dfs(o[i].u,,-);
edge[tmp].mark=edge[tmp^].mark=;
}
add(o[i].u,o[i].v,o[i].w);
add(o[i].v,o[i].u,o[i].w);
}
if(cnt==n-)
{
_max=;
dfs(,,-);
ans=min(ans,_max-o[].w);
}
if(ans==INF)printf("-1\n");
else printf("%I64d\n",ans);
}
return ;
}
上一篇:iOS之 Xcode7下 bitcode的工作流程及安全评估


下一篇:怎样在Ubuntu中设置环境变量