注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1977][BeiJing2010组队]次小生成树 Tree  

2014-08-22 20:34:14|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1977: [BeiJing2010组队]次小生成树 Tree

严格次小生成树
先是少写了一些东西
然后没有开long long
无限WA

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100000+10;
const int M = 300000+10;
const LL MAX = 1e17;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\n'||cc=='\r')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
struct Edge{
int a,b,c;
Edge(){}
Edge(int aa,int bb,int cc):a(aa),b(bb),c(cc){}
}edges[M];
bool cmp(Edge a,Edge b){return a.c<b.c;}
short sel[M];
int n,m;
struct Point{
Point(){next=NULL;}
int d,len;
Point *next;
void push(int a,int b){
Point *l = new Point;
l->next=next;next=l;
l->d=a;l->len=b;
}
}point[N];
int fa[N],size[N],deep[N];
int find(int x){if(!fa[x])return x;return fa[x]=find(fa[x]);}
bool merge(int a,int b,int c){
int ffa,ffb;
ffa=find(a);ffb=find(b);
if(ffa==ffb)return 0;
if(!size[ffa])size[ffa]++;
if(!size[ffb])size[ffb]++;
if(size[ffa]>size[ffb])swap(ffa,ffb);
fa[ffa]=ffb;
point[a].push(b,c);point[b].push(a,c);
return 1;
}
int anc[N][30],two[40];
LL weight1[N][30],weight2[N][30];
void update(int x,int k,LL val){
if(val==weight1[x][k]||val==weight2[x][k]) return;
if(val > weight1[x][k]){
weight2[x][k]=weight1[x][k];
weight1[x][k]=val;
}else if(val > weight2[x][k] ) weight2[x][k] = val;
}
int Anc(int x,int k){
if(anc[x][k])return anc[x][k];
if(two[k] > deep[x]-1) return 0;
int a;
anc[x][k]=Anc(a=Anc(x,k-1),k-1);
if(anc[x][k]){
update(x,k,weight1[x][k-1]);
update(x,k,weight2[x][k-1]);
update(x,k,weight1[a][k-1]);
update(x,k,weight2[a][k-1]);
}
return anc[x][k];
}
short v[N];
void dfs(int x){
v[x]=1;
for(Point *i = point[x].next;i!=NULL;i=i->next)
if(i->d!=anc[x][0]){
anc[i->d][0]=x;
update(i->d,0,i->len);
deep[i->d] = deep[x]+1;
if(!v[i->d])dfs(i->d);
}
}
LL get(int a,int b,int c){
if(deep[a] < deep[b])swap(a,b);
int k,ffa,ffb;
weight1[0][0]=weight2[0][0]=0;
for(k = log2(deep[a])+1;k>=0;k--)
if(deep[ffa=Anc(a,k)] >= deep[b]){
update(0,0,weight1[a][k]);
update(0,0,weight2[a][k]);
a=ffa;
}
if(a==b){
if(weight1[0][0]!=c)return c-weight1[0][0];
else if(weight2[0][0])return c-weight2[0][0];//*
else return 0;
}
for(k=log2(deep[b])+1;k>=0;k--)
if((ffa=Anc(a,k))!=(ffb=Anc(b,k))){
update(0,0,weight1[a][k]);
update(0,0,weight2[a][k]);
update(0,0,weight1[b][k]);
update(0,0,weight2[b][k]);
a=ffa;b=ffb;
}
update(0,0,weight1[a][0]);//*
update(0,0,weight2[a][0]);
update(0,0,weight1[b][0]);
update(0,0,weight2[b][0]);
if(weight1[0][0]!=c)return c-weight1[0][0];
else if(weight2[0][0])return c-weight2[0][0];
else return 0;
}
int main(){
int i,j,a,b;LL lans=MAX,ans=0;
freopen("input.txt","r",stdin);
freopen("p.txt","w",stdout);
n=scan();m=scan();
for(two[0]=1,i=1;i<=30;i++)two[i]=two[i-1]*2;
for(i=1;i<=m;i++){
a=scan();b=scan();
edges[i]=Edge(a,b,scan());
}
sort(edges+1,edges+m+1,cmp);
int left=n-1;
for(i=1;i<=m&&left;i++)
if((sel[i]=merge(edges[i].a,edges[i].b,edges[i].c)))left--,ans+=edges[i].c;
deep[1]=1;dfs(1);
//枚举
for(i=1;i<=m;i++)
if(!sel[i]){
LL aa=get(edges[i].a,edges[i].b,edges[i].c);
if(aa&&ans+aa<lans)lans=ans+aa;
}
printf("%lld\n",lans);
return 0;
}

题解:
性质:
次小生成树一定是由最小生成树换了一条边得到的
那么枚举每条不在次小生成树上的边,把它加入后会产生一个环,删掉环上最大的那条边
注意因为是”严格次小“所以要维护最大值和次大值
如果最大值和当新加入边一样就选次大边
求最大边用倍增
时间复杂度O(MlogN)(左右)
  评论这张
 
阅读(24)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017