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

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 1879继续畅通工程  

2014-04-04 23:13:51|  分类: 并查集 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |



Total Submission(s) : 9   Accepted Submission(s) : 4
Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全省畅通需要的最低成本。
 

Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。

当N为0时输入结束。
 

Output
每个测试用例的输出占一行,输出全省畅通需要的最低成本。
 

Sample Input
3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0
 

Sample Output
3
1
0
 

Author
ZJU
 

Source
浙大计算机研究生复试上机考试-2008年
 


#include<stdio.h>
#include<algorithm>
using namespace std;
int bin[110];
struct fins
{
int x,y;
int length;
int flag;
}joint[11000];
int find(int x)
{
int r=x;
while(r!=bin[r])
r=bin[r];
return r;
}
void inting()
{
int i;
for(i=0;i<=104;i++)
{
bin[i]=i;
}
}
void merge(int x,int y)
{
if(x<y)
bin[y]=x;
else
bin[x]=y;
}
bool cmp(struct fins x,struct fins y)
{
if(x.flag==1)
return true;
else if(y.flag==1)
{
return false;
}

return x.length<y.length;
}
int main()
{
int m,i,sum,count,n,k,l;
while(scanf("%d",&m),m)
{
n=m*(m-1)/2;
sum=0;
count=0;
inting();
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d",&joint[i].x,&joint[i].y,&joint[i].length,&joint[i].flag);
}
sort(joint+1,joint+n+1,cmp);

for(i=1;i<=n;i++)
{
k=find(joint[i].x);
l=find(joint[i].y);

if(k!=l)
{
count++;
merge(k,l);
if(joint[i].flag==0)
sum+=joint[i].length;
if(count==m-1) 
break;
}
}
printf("%d\n",sum);


}
return 0;
}

/*#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int find(int);
struct Relation
{
int x,y;
int value,state;
};
Relation real[11000],fake[11000],temp;
int cmp(Relation a,Relation b)
{
return a.value<b.value;
}
int fa[110];
inline void format()
{
for(int i=0;i<=100;i++)
fa[i]=i;
}
inline bool run(int x,int y)
{
int numx=find(x);
int numy=find(y);
if(numx!=numy)
{
fa[numx]=numy;
return true;
}
return false;
}
inline int find(int i)
{
while(i!=fa[i])
i=fa[i];
return i;
}
int main()
{
int n,m,i;
while(scanf("%d",&m)!=EOF)
{
if(m==0) break;
format();
int count=0;
int money=0;
int numofreal=0;
int numoffake=0;
n=m*(m-1)/2;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&temp.x,&temp.y,&temp.value,&temp.state);
if(temp.state==0)
fake[numoffake++]=temp;
else
real[numofreal++]=temp;
}
for(i=0;i<numofreal;i++)
{
if(run(real[i].x,real[i].y))
count++;
}
if(count<m-1)
{
sort(fake,fake+numoffake,cmp);
for(i=0;i<numoffake;i++)
{
if(run(fake[i].x,fake[i].y))
{
count++;
money+=fake[i].value;
}
if(count==m-1) break;
}
if(count==m-1)
printf("%d\n",money);
}
else
printf("%d\n",0);
}
return 0;
}
两种不同的方法


#include<stdio.h>
#include<algorithm>
using namespace std;
int bin[110];
struct fins
{
int x,y;
int length;
int flag;
}joint[11000];
int find(int x)
{
int r=x;
int i,j;
while(r!=bin[r])
r=bin[r];
i=x;
while(i!=r)
{
j=bin[i];
bin[i]=r;
i=j;
}
return r;
}
void inting(int x)
{
int i;
for(i=1;i<=x;i++)
{
bin[i]=i;
}
}
void merge(int x,int y)
{
bin[x]=y;
}
bool cmp( fins x, fins y)
{
if(x.flag==1)
return true;
else if(y.flag==1)
{
return false;
}
if( x.length<y.length)
return true;
return false;
}
int main()
{
int m,i,sum,count,n,k,l;
while(scanf("%d",&m),m)
{
n=m*(m-1)/2;
sum=0;
count=0;
inting(m);
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d",&joint[i].x,&joint[i].y,&joint[i].length,&joint[i].flag);
}
sort(joint+1,joint+n+1,cmp);


for(i=1;i<=n;i++)
{
k=find(joint[i].x);
l=find(joint[i].y);

if(k!=l)
{
count++;
merge(k,l);
if(joint[i].flag==0)
sum+=joint[i].length;
if(count==m-1)
break;
}
}
printf("%d\n",sum);


}
return 0;
}改进版本A!

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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