HDU 5441 Travel
Travel
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Description
Input
For each test case, the first line consists of three integers $n, m$ and $q$ where $n \leq 20000, m \leq 100000, q \leq 5000$. The Undirected Kingdom has $n$ cities and $m$ bidirectional roads, and there are $q$ queries.
Each of the following $m$ lines consists of three integers $a, b$ and $d$ where $a, b ∈ \{1, . . . , n\}$ and $d \leq 100000$. It takes Jack $d$ minutes to travel from city $a$ to city $b$ and vice versa.
Then $q$ lines follow. Each of them is a query consisting of an integer $x$ where $x$ is the time limit before Jack goes berserk.
Output
Note that $(a, b)$ and $(b, a)$ are counted as different pairs and $a$ and $b$ must be different cities.
Sample Input
Sample Output
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
using LL = long long;
int uf[maxn];
LL ret,ans[maxn],cnt[maxn];
struct arc {
int u,v,w;
bool operator<(const arc &rhs) const {
return w < rhs.w;
}
} e[];
struct QU {
int w,id;
bool operator<(const QU &rhs) const{
return w < rhs.w;
}
} Q[maxn];
int Find(int x) {
if(x != uf[x]) uf[x] = Find(uf[x]);
return uf[x];
}
bool Union(int x,int y) {
x = Find(x);
y = Find(y);
if(x == y) return false;
ret -= cnt[x]*(cnt[x] - ) + cnt[y]*(cnt[y] - );
ret += (cnt[x] + cnt[y])*(cnt[x] + cnt[y] - );
if(cnt[x] < cnt[y]) {
uf[x] = y;
cnt[y] += cnt[x];
cnt[x] = ;
} else {
uf[y] = x;
cnt[x] += cnt[y];
cnt[y] = ;
}
return true;
}
int main() {
int kase,n,m,q;
scanf("%d",&kase);
while(kase--) {
scanf("%d%d%d",&n,&m,&q);
for(int i = ; i < m; ++i)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
for(int i = ; i < q; ++i) {
scanf("%d",&Q[i].w);
Q[i].id = i;
}
sort(e,e + m);
sort(Q,Q + q);
for(int i = ; i <= n; ++i) {
uf[i] = i;
cnt[i] = ;
}
ret = ;
for(int i = ,j = ; i < q; ++i) {
while(j < m && e[j].w <= Q[i].w) {
Union(e[j].u,e[j].v);
++j;
}
ans[Q[i].id] = ret;
}
for(int i = ; i < q; ++i)
printf("%I64d\n",ans[i]);
}
return ;
}
最新文章
- python远程连接paramiko 模块和堡垒机实现
- dhtmlx相关
- 数据库MySQL开篇
- 初学UML——用例图
- [Effective JavaScript 笔记] 第11条:熟练掌握闭包
- Hadoop:使用原生python编写MapReduce
- SVN客户端解决authorization failed问题
- 关于androidManifest.xml的概叙以及intent-filter的详细分析
- UITableViewCell 高度自适应
- uniq linux下去除重复行命令
- Mybatis 学习历程
- TCP/IP详解之:广播和多播
- javascript 限制字符串字数换行 带BUG
- Java的动态加载及其安全性问题
- iis7.0 ExtensionlessUrlHandler-Integrated-4.0解决方法
- [GitHub]第四讲:合并分支
- js 判断js,css是否引入,确保不重复引入
- 分布式计算课程补充笔记 part 1
- react中组件的渲染
- 解题:国家集训队 Middle