codevs 1231 最优布线问题 x（find函数要从娃娃抓起系列）
学校需要将n台计算机连接起来，不同的2台计算机之间的连接费用可能是不同的。为了节省费用，我们考虑采用间接数据传输结束，就是一台计算机可以间接地通过其他计算机实现和另外一台计算机连接。
为了使得任意两台计算机之间都是连通的（不管是直接还是间接的），需要在若干台计算机之间用网线直接连接，现在想使得总的连接费用最省，让你编程计算这个最小的费用。
输入第一行为两个整数n,m（2<=n<=100000，2<=m<=100000），表示计算机总数，和可以互相建立连接的连接个数。接下来m行，每行三个整数a,b,c 表示在机器a和机器b之间建立连接的话费是c。(题目保证一定存在可行的连通方案, 数据中可能存在权值不一样的重边，但是保证没有自环)
输出只有一行一个整数，表示最省的总连接费用。
3 3
1 2 1
1 3 2
2 3 1
2
最终答案需要用long long类型来保存
分类标签 Tags 点此展开
(把find(f[x]改为f[x]=find(f[x])))
这样一个处理！
不然数据越大，越难弄，需要从低向上找很久很久
运行结果
测试点#1.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#2.in 结果:AC 内存使用量: 492kB 时间使用量: 15ms
测试点#3.in 结果:AC 内存使用量: 620kB 时间使用量: 26ms
测试点#4.in 结果:TLE 内存使用量: 3176kB 时间使用量: 1000ms
测试点#5.in 结果:TLE 内存使用量: 2924kB 时间使用量: 1000ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define Maxn 100010 using namespace std; long long n,m,tot=,f1,f2,k;
long long f[Maxn];
bool u[Maxn]; struct gx{
long long x;
long long y;
long long w;
bool operator < (const gx &qwq)const
{
return w<qwq.w;
}
}gx[Maxn]; int find(int x)
{
//if(f[x]!=x) f[x]=find(f[x]);
//return f[x];
return x == f[x] ? x : find(f[x]);
} int main()
{
//ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=m;i++)
{
cin>>gx[i].x>>gx[i].y>>gx[i].w;
}
for(int i=;i<=n;i++) f[i]=i;
sort(gx+,gx++m);
for(int i=;i<=m;i++)
{
f1=find(gx[i].x);
f2=find(gx[i].y);
if(f1!=f2)
{
f[f2]=f1;
++k;
tot+=gx[i].w;
}
if(k==n-) break;
}
cout<<tot<<endl;
return ;
}
AC的两个代码：
1）原因仅仅是因为把find函数改了
数据如下：
运行结果
测试点#1.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#2.in 结果:AC 内存使用量: 488kB 时间使用量: 12ms
测试点#3.in 结果:AC 内存使用量: 744kB 时间使用量: 25ms
测试点#4.in 结果:AC 内存使用量: 3052kB 时间使用量: 147ms
测试点#5.in 结果:AC 内存使用量: 2920kB 时间使用量: 142ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define Maxn 100010 using namespace std; long long n,m,tot=,f1,f2,k;
long long f[Maxn];
bool u[Maxn]; struct gx{
long long x;
long long y;
long long w;
bool operator < (const gx &qwq)const
{
return w<qwq.w;
}
}gx[Maxn]; int find(int x)
{
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
//return x == f[x] ? x : find(f[x]);
} int main()
{
//ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=m;i++)
{
cin>>gx[i].x>>gx[i].y>>gx[i].w;
}
for(int i=;i<=n;i++) f[i]=i;
sort(gx+,gx++m);
for(int i=;i<=m;i++)
{
f1=find(gx[i].x);
f2=find(gx[i].y);
if(f1!=f2)
{
f[f2]=f1;
++k;
tot+=gx[i].w;
}
if(k==n-) break;
}
cout<<tot<<endl;
return ;
}
2）优化版（把cin，cout优化）
代码：
数据：
运行结果
测试点#1.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#2.in 结果:AC 内存使用量: 492kB 时间使用量: 4ms
测试点#3.in 结果:AC 内存使用量: 616kB 时间使用量: 10ms
测试点#4.in 结果:AC 内存使用量: 3180kB 时间使用量: 60ms
测试点#5.in 结果:AC 内存使用量: 3048kB 时间使用量: 54ms
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define Maxn 100010 using namespace std; long long n,m,tot=,f1,f2,k;
long long f[Maxn];
bool u[Maxn]; struct gx{
long long x;
long long y;
long long w;
bool operator < (const gx &qwq)const
{
return w<qwq.w;
}
}gx[Maxn]; int find(int x)
{
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
//return x == f[x] ? x : find(f[x]);
} int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=m;i++)
{
cin>>gx[i].x>>gx[i].y>>gx[i].w;
}
for(int i=;i<=n;i++) f[i]=i;
sort(gx+,gx++m);
for(int i=;i<=m;i++)
{
f1=find(gx[i].x);
f2=find(gx[i].y);
if(f1!=f2)
{
f[f2]=f1;
++k;
tot+=gx[i].w;
}
if(k==n-) break;
}
cout<<tot<<endl;
return ;
}
最新文章
- CE 消息处理
- 11039 - Building designing
- windows Server 2008 IE增强的安全配置关闭方法
- SQL：一句话删除重复的数据
- Android系统SVC命令教程
- 使用自定义 URL 实现控制器之间的跳转-b
- 01_反射_04_反射类的main方法
- struts2文件异步上传
- 我所理解的OOP——UML六种关系（转）
- 2014/09/30 Learning Note
- Apache Struts 多个开放重定向漏洞(CVE-2013-2248)
- -_-#【Better JS Code】严格模式
- android快捷简单的实现音乐播放器
- 正在搞用web.py做的通讯录
- Ruby中的Symbol与字符串
- [RxJS] Reactive Programming - Using cached network data with RxJS -- withLatestFrom()
- ****微信小程序架构解析
- Java基础 -- final关键字
- android经典源码，很不错的开源框架
- CentOS7搭建jdk