HDU——1233还是畅通工程(克鲁斯卡尔+优先队列)
2024-08-30 03:29:48
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 38031 Accepted Submission(s): 17161
Problem Description
某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
当N为0时,输入结束,该用例不被处理。
当N为0时,输入结束,该用例不被处理。
Output
对每个测试用例,在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
5
Hint
Hint
Huge input, scanf is recommended.
WA好几次发现是顶点数搞错了和数组开小了……
代码:
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long LL;
struct info
{
int x,y,v;
bool operator<(const info &b) const
{
return v>b.v;
}
};
const int N=5000;
int pre[N],ran[N];
inline int find(int n)
{
if(n!=pre[n])
return pre[n]=find(pre[n]);
return pre[n];
}
inline bool joint(int a,int b)
{
int fa=find(a),fb=find(b);
if(fa!=fb)
{
if(ran[fa]>ran[fb])
{
pre[fb]=fa;
ran[fa]+=ran[fb];
}
else
{
pre[fa]=fb;
ran[fb]+=ran[fa];
}
return true;
}
return false;
}
int main(void)
{
int n,i,m;
while (~scanf("%d",&n)&&n)
{
MM(pre);MM(ran);
m=(n*(n-1))>>1;
for (i=0; i<=n; i++)
{
pre[i]=i;
ran[i]=1;
}
priority_queue<info> Q;
info t;
for (i=0; i<m; i++)
{
scanf("%d%d%d",&t.x,&t.y,&t.v);
Q.push(t);
}
int ans=0,cnt=0;
while (!Q.empty())
{
if(cnt==n-1)
break;
info now=Q.top();
Q.pop();
if(joint(now.x,now.y))
{
ans+=now.v;
cnt++;
}
}
printf("%d\n",ans);
}
return 0;
}
最新文章
- 对jquery分页的升级
- centos 7 中 tomcat 安装
- hadoop 根据SecondaryNameNode恢复Namenode
- dedecms 根据key取得联动类型(enum)值
- Fire Net(深搜 和一前不一样的深搜)
- registered the JBDC driver [oracle.jdbc.OracleDriver] but failed to unregister it when the web application was stopped. (转)
- Xcode7 使用NSURLSession发送HTTP请求报错
- DLL运行时动态加加载的问题
- css3 的 calc()函数在布局中的使用----头部高度固定,页面正好占满一屏
- ApplicationContextAware
- django集成ansibe实现自动化
- PRD是什么
- 从前端中的IOC理念理解koa中的app.use()
- 如何调整cell的大小
- gamma函数及相关其分布
- C#中.XSD是什么文件?
- C#计算两个日期之间相差的天数
- eclipse添加dtd约束和xml约束的方法
- 改变random.seed()种子值,获取不同的随机值
- VC++ 监视文件(夹)