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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3669][Noi2014]魔法森林  

2014-08-28 13:11:01|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3669: [Noi2014]魔法森林

又是一道LCT题。。
当时网上同步赛的时候用的并査集做的,大概搞到50多分(用SPFA能A真是不科学
当时因为水管局长实在调不出来了所以在claris神犇建议下改做这个题。。
结构又死活都不对
最后实在受不了了
用Graphviz把每一步的情况都画了出来= =、终于找到问题
水管局长+这个题LCT大概写了有5遍了QuQ
至少维护动态MST的题目基本是能写出来了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX = 1e9;
const int N = 50000+10;
const int M = 50000*2+10;
int n,m;
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')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 Node{
Node();
int d,bh;short flag;
Node *fa,*ch[2],*best;
short pl(){return this==fa->ch[0]?0:1;}
void push();void count();
}house[M],point[N],*null;int hn;
queue<Node*>pupa;
Node *newNode(){
if(hn < M){house[hn] = Node();house[hn].best = &house[hn];return &house[hn++];}
if(pupa.empty())return new Node();
Node *r = pupa.front();pupa.pop();
*r = Node();r->best = r;return r;
}
void del(Node *&r){pupa.push(r);r = null;}
Node::Node(){fa=ch[0]=ch[1]=null;best=this;d=bh=flag=0;}
void Node::push(){
if(this == null)return;
if(flag){
swap(ch[0],ch[1]);
ch[0]->flag^=1;
ch[1]->flag^=1;
flag=0;
}
}
void Node::count(){
if(this == null)return;
best=this;
if(ch[0]->best->d > best->d)best=ch[0]->best;
if(ch[1]->best->d > best->d)best=ch[1]->best;
}
struct LCT{
LCT(){
null = newNode();
null->ch[0]=null->ch[1] = null->fa = null;
}
bool notr(Node *r){return r->fa->ch[0]==r||r->fa->ch[1]==r;}
void rotate(Node *k){
Node *r = k->fa;if(r==null||k==null)return;
r->push();k->push();
int x = k->pl()^1;
r->ch[x^1] = k->ch[x];
r->ch[x^1]->fa = r;
if(r->fa!=null&&notr(r)) r->fa->ch[r->pl()] = k;//*
k->fa = r->fa;r->fa = k;
k->ch[x] = r;
r->count();k->count();
}
void splay(Node *r){
for(;notr(r);rotate(r))
if(notr(r->fa))rotate(r->pl()==r->fa->pl()?r->fa:r);
r->push();//*
}
Node *root(Node *r){
hello(r);splay(r);
while(r->ch[0]!=null)r=r->ch[0];
return r;
}
Node *hello(Node *r){
Node *l = null;
for(;r!=null;l=r,r=r->fa){
splay(r);
(r->ch[1]=l)->fa=r;
r->count();
}return l;
}
void changer(Node *r){
hello(r)->flag^=1;
splay(r);
}
void cut(Node *r,Node *l){
changer(r);
hello(l);splay(l);
l->ch[0] = r->fa = null;//*
l->count();//*
}
void link(Node *r,Node *l){
changer(r);
r->fa = l;
hello(r);
}
Node *ask(Node *r,Node *l){
changer(r);
hello(l);splay(l);
return l->best;
}
}lt;
struct Edge{
int a,b,c,d;
Edge(){}
Edge(int aa,int bb,int cc,int dd):a(aa),b(bb),c(cc),d(dd){if(a>b)swap(a,b);}
}edges[M];
bool operator < (Edge a,Edge b){return a.c<b.c;}
int main(){
int i,j,a,b,c;
n=scan();m=scan();
for(i=1;i<=n;i++) point[i]=Node(),point[i].best = &point[i],point[i].bh=-i;
for(i=1;i<=m;i++){
a=scan();b=scan();c=scan();
edges[i]=Edge(a,b,c,scan());
}
sort(edges+1,edges+1+m);
int ans=MAX;
for(i=1;i<=m;i++){
a=edges[i].a;b=edges[i].b;
if(lt.root(&point[a])!=lt.root(&point[b])){
Node *r = newNode();r->bh=i;r->d = edges[i].d;
lt.link(r,&point[a]);
lt.link(r,&point[b]);
}else{
Node *r=lt.ask(&point[a],&point[b]);
if(edges[i].d < r->d){
lt.cut(r,&point[edges[r->bh].a]);
lt.cut(r,&point[edges[r->bh].b]);
r = newNode();r->bh=i;r->d = edges[i].d;
lt.link(r,&point[a]);
lt.link(r,&point[b]);
}
}
if(lt.root(&point[1])==lt.root(&point[n]))
ans = min(ans,edges[i].c+lt.ask(&point[1],&point[n])->d);
}
if(ans==MAX)ans=-1;
printf("%d\n",ans);
return 0;
}

题解:
把边按照a从小到大排序,然后依次加边动态维护b的MST,每次更新答案
这就相当于枚举了每个在a最大值确定的时候b的最优情况
最后:我的DEBUG用代码
需要用Graphviz这个软件把图画出来。。

/*---------------------------DEBUG------------------------------*/
bool notr(Node *r){return r==r->fa->ch[0]||r==r->fa->ch[1];}
int on=0,FLAG=1,PAINT=0;FILE *OUT;
short pv[N],ev[N];
void print(Node*r){
if(FLAG)r->push();
if(r->ch[0]!=null){
//fprintf(OUT,"%d -> %d\n",r->ch[0]->bh,r->bh);
fprintf(OUT,"%d -> %d [label = 0]\n",r->bh,r->ch[0]->bh);
if(!((r->ch[0]->bh > 0&&ev[r->ch[0]->bh])||(r->ch[0]->bh < 0&&pv[-r->ch[0]->bh])))
print(r->ch[0]);
}
if(!notr(r)&&r->fa!=null){
fprintf(OUT,"%d -> %d [color = red]\n",r->fa->bh,r->bh);
if(!((r->fa->bh > 0&&ev[r->fa->bh])||(r->fa->bh < 0&&pv[-r->fa->bh])))print(r->fa);
}
if(r->bh>0)//edge
fprintf(OUT,"%d [label = \"%d E[%d]\"][shape = box]\n",r->bh,r->bh,r->d),ev[r->bh]=1;
else
fprintf(OUT,"%d [label = \"%d P\"]\n",r->bh,-r->bh),pv[-r->bh]=1;

fprintf(OUT,"%d -> %d [style = dotted]\n",r->bh,r->best->bh);
if(r->ch[1]!=null){
//fprintf(OUT,"%d -> %d\n",r->ch[1]->bh,r->bh);
fprintf(OUT,"%d -> %d [label = 1]\n",r->bh,r->ch[1]->bh);
if(!((r->ch[1]->bh > 0&&ev[r->ch[1]->bh])||(r->ch[1]->bh < 0&&pv[-r->ch[1]->bh])))
print(r->ch[1]);
}
}
void output(){
if(!PAINT) return;
on++;char file[20];
sprintf(file,"graph%d.dot",on);
OUT = fopen(file,"w");
fprintf(OUT,"digraph{\n");
memset(pv,0,sizeof(pv));
memset(ev,0,sizeof(ev));
for(int i=1;i<=n;i++)
if(!pv[i]){
Node *r = &point[i];
while(notr(r))r=r->fa;
print(r);
}
fprintf(OUT,"}\n");
fclose(OUT);
}
/*---------------------------DEBUG------------------------------*/


  评论这张
 
阅读(18)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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