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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2753][SCOI2012]滑雪与时间胶囊  

2014-11-12 20:36:28|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2753: [SCOI2012]滑雪与时间胶囊

比较有技巧的题
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1E5+10;
const int M = 1E6+10;
int n,m,all;
int fa[N],h[N];
short v[N];
struct Edge{
int a,b,len;
Edge(){}
Edge(int aa,int bb,int c):a(aa),b(bb),len(c){}
}edges[M];
/*bool operator < (Edge a,Edge b){
if(h[a.a]==h[b.a]){
if(h[a.b]==h[b.b])return a.len < b.len;
return h[a.b] > h[b.b];
}return h[a.a] > h[b.a];
}*/
bool operator < (Edge a,Edge b){return h[a.b] == h[b.b]?a.len < b.len:h[a.b] > h[b.b];}
struct Point{
Point(){next = NULL;}
Point *next;int d;
void push(int);
}point[N],house[M];int hn;
Point *newPoint(){
if(hn < M)return &house[hn++];
return new Point;
}
void Point::push(int a){
Point *l = newPoint();
l->next = next;next = l;
l->d=a;
}
//int scan(){int i=0;scanf("%d",&i);return i;}
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 fh*re;
}
int find(int x){if(!fa[x])return x;return fa[x] = find(fa[x]);}
queue<int>dui;
int main(){
//freopen("in.txt","r",stdin);
//freopen("ski.in","r",stdin);
int i,j,a,b,c;
n = scan();m = scan();
for(i=1;i<=n;i++)h[i] = scan();
for(i=1;i<=m;i++){
a = scan();b = scan();c = scan();
if(h[a] < h[b])swap(a,b);
edges[i] = Edge(a,b,c);
point[a].push(b);
if(h[a] == h[b])
point[b].push(a);
}
dui.push(1);v[1] = 1;all=1;
while(!dui.empty()){
int now = dui.front();dui.pop();
for(Point *l = point[now].next;l!=NULL;l=l->next)
if(!v[l->d] && h[now] >= h[l->d])dui.push(l->d),all++,v[l->d]=1;
}
sort(edges+1,edges+1+m);
int left = all-1;
long long ans=0;
for(i=1;i<=m;i++){
a = edges[i].a;
b = edges[i].b;
if((!v[a]) || (!v[b]))continue;
//if(h[a] < h[b])continue;
//if(h[a] > h[b] && find(a)!=find(1))continue;
a = find(a);b = find(b);
if(a!=b){
if(i&1) fa[a] = b;
else fa[b] = a;
ans += edges[i].len;
left--;
if(!left)break;
}
}
printf("%d %lld\n",all,ans);
return 0;
}

题解:
最小生成树
首先第一问很好判,BFS一遍就OK,不可达的点全部删掉
然后是第二问,有向图的最小生成树……
也叫最小树形图
据说标准的要用朱-刘算法
不过用这一算法会T。。
但是这题有一个高度这一神奇的性质
没有被删的点集中,去掉所有的双向边(高度相同的),剩下的是一张DAG
(我一开始是以为无论怎么选都一定是合法的,但后来发现可能会出现奇怪的情况,比如会出现高的点从低的点走到)
为了保证合法,我们把图分层,从高到低一层一层建树。
具体实现方法就是把边按照终点高度为第一关键字,边长为第二关键字排序再做kruskal
  评论这张
 
阅读(18)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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