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

ydc的博客

 
 
 

日志

 
 

bzoj 1196 (hnoi2006) 公路修建  

2013-03-27 23:47:39|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
挺水的
二分一个答案,并查集乱搞就行了啦
虽然我好看上去很高级的写了个克鲁斯卡尔??
是我无聊了
还有数据有点问题,具体见discuss

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 10010
#define MAXM 40010
using namespace std;
struct node
{
int x,y,c1,c2;
}road[MAXM];
struct Edge
{
int x,y,len;
Edge() {}
Edge(int x,int y,int len): x(x),y(y),len(len) {}
friend bool operator < (const Edge &a,const Edge &b){ return a.len<b.len; }
}edge[MAXM];
int n,m,k,father[MAXN];
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
void read()
{
Read(n),Read(k),Read(m),m--;
for(int i=1;i<=m;i++)
Read(road[i].x),Read(road[i].y),Read(road[i].c1),Read(road[i].c2);
}
int Find(int p)
{
if(father[p]==p) return p;
father[p]=Find(father[p]);
return father[p];
}
bool check(int p)
{
int tot=0;
for(int i=1;i<=m;i++)
{
if(road[i].c1<=p) edge[++tot]=Edge(road[i].x,road[i].y,0),edge[++tot]=Edge(road[i].y,road[i].x,0);
else if(road[i].c2<=p) edge[++tot]=Edge(road[i].x,road[i].y,1),edge[++tot]=Edge(road[i].y,road[i].x,1);
}
sort(edge+1,edge+tot+1);
int MST=0;
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=tot;i++)
{
int x=Find(edge[i].x),y=Find(edge[i].y);
if(x!=y) father[x]=y,MST+=edge[i].len;
}
int cnt_root=0;
for(int i=1;i<=n;i++)
cnt_root=cnt_root+(Find(i)==i);
return n-MST>k&&cnt_root==1;
}
int Find(int l,int r)
{
while(l<r)
{
int mid=(l+r)>>1;
if(!check(mid)) l=mid+1;
else r=mid;
}
return l;
}
int main()
{
read();
printf("%d\n",Find(1,30000));
return 0;
}




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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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