Lightoj1059【最小生成树】
2024-08-30 04:49:49
题意:
使得所有的位置都能通向一个机场,问最小花费。
思路:
最小生成树。
本来还想标记一下没有出现过的点,其实那个数组已经解决了。==。
PS:注意路比建造机场还贵?直接造机场得了?
if there are several answers with minimal cost, choose the one that maximizes the number of airports.
而且相等也是造机场~
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
bool vis[N];
int pre[N],n,m,t;
struct Node{
int x,y,w;
}q[N];
bool cmp(Node a,Node b)
{
return a.w<b.w;
} int Find(int x)
{
int r=x;
while(pre[r]!=r)
r=pre[r];
int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
} int main()
{
int T,cas=1;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
{
pre[i]=i;
vis[i]=false;
}
for(int i=0;i<m;++i)
scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].w);
sort(q,q+m,cmp);
int ans=0,cnt=0;
for(int i=0;i<m&&q[i].w<t;i++)
{
int x=Find(q[i].x);
int y=Find(q[i].y);
vis[q[i].x]=vis[q[i].y]=true;
if(x!=y)
{
pre[x]=y;
ans+=q[i].w;
}
}
for(int i=1;i<=n;i++)
if(pre[i]==i)
{
ans+=t;
cnt++;
}
printf("Case %d: %d %d\n",cas++,ans,cnt);
}
return 0;
} /* 5 3 10
1 2 1
3 4 1
4 5 11
Case 1: 32 3 */
最新文章
- TCP/IP中链路层的附加数据(Trailer数据)和作用
- JavaScript 框架设计
- my_shell
- java 23种设计模式及具体例子 收藏有时间慢慢看
- 【NOI2006】最大获利
- 【转】Android源码学习(2)使用Git和Repo进行版本管理
- 设计模式——观察者模式(C++实现)
- BZOJ_3653_谈笑风生_树状数组
- mplayer用法收集【转】
- 猜数字游戏,判断输入的数字与系统产生的数字是否一致(Math.random()与if嵌套循环)
- 【jquery采坑】Ajax配合form的submit提交(微擎表单提交,ajax验证,submit提交)
- Android View体系(四)从源码解析Scroller
- Nginx中防盗链(下载防盗链和图片防盗链)及图片访问地址操作记录
- mq命令帮助文档
- 执行力:Just Do It
- HDU5320 : Fan Li
- [转]“菜”鸟理解.NET Framework(CLI,CLS,CTS,CLR,FCL,BCL)
- [TJOI2014]Alice and Bob[拓扑排序+贪心]
- 用到的C++标准库
- Error: A JNI error has occurred, please check your installation and try again