[JOYOI1307] 联络员
2024-08-31 14:45:01
题目限制
时间限制 | 内存限制 | 评测方式 | 题目来源 |
1000ms | 131072KiB | 标准比较器 | Local |
题目描述
Tyvj已经一岁了,网站也由最初的几个用户增加到了上万个用户,随着Tyvj网站的逐步壮大,管理员的数目也越来越多,现在你身为Tyvj管理层的联络员,希望你找到一些通信渠道,使得管理员两两都可以联络(直接或者是间接都可以)。Tyvj是一个公益性的网站,没有过多的利润,所以你要尽可能的使费用少才可以。
目前你已经知道,Tyvj的通信渠道分为两大类,一类是必选通信渠道,无论价格多少,你都需要把所有的都选择上;还有一类是选择性的通信渠道,你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。
输入格式
第一行n,m表示Tyvj一共有n个管理员,有m个通信渠道
第二行到m+1行,每行四个非负整数,p,u,v,w 当p=1时,表示这个通信渠道为必选通信渠道;当p=2时,表示这个通信渠道为选择性通信渠道;u,v,w表示本条信息描述的是u,v管理员之间的通信渠道,u可以收到v的信息,v也可以收到u的信息,w表示费用。
输出格式
最小的通信费用
提示
样例解释:
1-2-3-4-1存在四个必选渠道,形成一个环,互相可以到达。需要让所有管理员联通,需要联通2和5号管理员,选择费用为5的渠道,所以总的费用为9
注意:
U,v之间可能存在多条通信渠道,你的程序应该累加所有u,v之间的必选通行渠道
数据范围:
对于30%的数据,n<=10 m<=100
对于50%的数据, n<=200 m<=1000
对于100%的数据,n<=2000 m<=10000
样例数据
输入样例 #1 | 输出样例 #1 |
---|---|
5 6 |
9 |
提交地址 : JOYOI1307
题解:
水题;
考试考过;
Code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int n, m; struct edge
{
int x, y, val;
bool operator < (edge a){return val < a.val;}
}ed[];
int cnt;
inline void add(int x, int y, int z)
{
cnt++;
ed[cnt] = (edge){x, y, z};
}
int bi[], top;
int fa[];
inline int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
int ans = ;
int tot; int main()
{
cin >> n >> m;
for (register int i = ; i <= m ; i ++)
{
int p, x, y, z;
scanf("%d%d%d%d", &p, &x,&y, &z);
add(x, y, z);
if (p == ) bi[++top] = cnt;
} for (register int i = ; i <= n ; i ++) fa[i] = i;
for (register int i = ; i <= top ; i ++)
{
int fx = Find(ed[bi[i]].x) , fy = Find(ed[bi[i]].y);
if (fx != fy) tot++;
ans += ed[bi[i]].val;
fa[fx] = fy;
}
sort(ed + , ed + + cnt);
for (register int i = ; i <= cnt ; i ++)
{
int fx = Find(ed[i].x), fy = Find(ed[i].y);
if (fx == fy) continue;
fa[fx] = fy;
ans += ed[i].val;
tot++;
if (tot == n - ) break;
}
cout << ans << endl;
return ;
}
最新文章
- 前端学HTTP之代理
- Psp个人软件开发软件需求分析和用例分析
- 渣渣小本求职复习之路每天一博客系列——TCP/IP协议栈(5)
- linux系统的任务计划crontab使用详解
- 深入剖析iLBC的丢包补偿技术(PLC)
- LBS优化方案探究
- 引入代码后,在@override报错
- jQuery AJAX load() 方法
- 使用SourceTree将bitbucket的远程仓库回滚到某一次提交-b
- uploadify 自定义按钮样式
- HDU 5933 ArcSoft&#39;s Office Rearrangement 【模拟】(2016年中国大学生程序设计竞赛(杭州))
- eclipse(myEclipse) 配置maven项目
- 配置Tomcat中的Context元素中的中文问题
- 使用python将mysql数据库的数据转换为json数据
- response.sendRedirect 报 java.lang.IllegalStateException 异常的解决思路
- CC攻击网站和游戏如何针对性预防?
- Node.js 逐行读取
- react16 渲染流程
- 64 位 Windows 平台开发注意要点之文件系统重定向
- django 创建视图和APP