给一个无向图,求有多少个点对,使得两点间的路径上的花费小于L,这里路径上的花费是这样规定的,a、b两点之间所有的路径中的最大边的最小值。
当然题目上不是这么写的。它问的是有多少种路径,这里就比较模糊了,到底两个路径怎样才算是两种路径呢,这时候重新看题,可以发现,如果理解为路径中经过的点不同的话,题目中给的所谓两点间的花费这个定义就没有意义了,所以就可以猜测,题目要求的是有多少个点对了。
然后就明确题意后,再进行分析。对一个点对的所有路径,只要最短最大边的那条路径出现,其后的所有较大最大边的路径都是毫无意义的,那么不妨将所有的边按照权值从小对大进行排序,用并查集的方法,进行加边,已经连通的点就不再管。那么每次加边的时候,是将两个集合并在一起的过程,假设集合大小分为a,b,显然路径的种类是a*b个,此时对于所有大于集合中最大边的L,都要加上这个种类数了。
那么,算法就明确了,为离线算法,先输入所有的边和L,对所有的L进行排序,对所有的边进行排序,都为从小到大,然后对每个L,将比其小的边权的边都并在一起,计算种类数即可。
/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 2000000000
#define MAXN 10005
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int n, m, q;
int father[MAXN], num[MAXN];
long long out[MAXN];
struct node
{
int u, v, w;
bool operator <(const node &a)const
{
return w < a.w;
}
}edge[MAXN * 10];
struct wen
{
int l, id;
bool operator <(const wen &a)const
{
return l < a.l;
}
}p[MAXN];
void init()
{
for(int i = 1; i <= n; i++)
{
father[i] = i;
num[i] = 1;
}
}
int find(int x)
{
if(father[x] == x) return x;
int t = find(father[x]);
father[x] = t;
return t;
}
int join(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx == fy) return 0;
int t = num[fx] * num[fy];
num[fx] += num[fy];
num[fy] = 0;
father[fy] = fx;
return t;
}
int main()
{
while(scanf("%d%d%d", &n, &m, &q) != EOF)
{
init();
for(int i = 1; i <= m; i++)
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
sort(edge + 1, edge + m + 1);
for(int i = 1; i <= q; i++)
{
scanf("%d", &p[i].l);
p[i].id = i;
}
sort(p + 1, p + q + 1);
int pos = 1;
long long ans = 0;
for(int i = 1; i <= q; i++)
{
while(pos <= m && edge[pos].w <= p[i].l)
{
ans += join(edge[pos].u, edge[pos].v);
pos ++;
}
out[p[i].id] = ans;
}
for(int i = 1; i <= q; i++)
printf("%I64d\n", out[i]);
}
return 0;
}
分享到:
相关推荐
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集
使用并查集+贪心:先将已有边的权值从大到小排序,又n个点只需n-1条边,这时再遍历一遍,将有边的两点合并为一个队伍,当边的数量达到n-1时退出循环,因为此时已达到最小生成树。 边的权值由大到小排序是因为要将大...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
一、内容 TT and FF are ... friends. Uh... very very good friends -________-b FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game....
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
经典算法:(二分匹配,背包专题,筛选法,简单数学题,贪心算法,递推求解,动态规划,并查集,母函数,搜索,组合博弈等入门算法)
自己做的HDU ACM已经AC的题目