HDU3938 Portal 및 검색
2167 단어 함께 조사하여 모으다
7 2 1
6 8 3
4 5 8
5 8 2
2 8 9
6 4 5
2 1 5
8 10 5
7 3 7
7 8 8
10//조회 길이
6
1
5
9
1
8
2
7
6
#include
#include
#include
#include
using namespace std;
const int M = 10005;
/*
, ,
, , , 。
*/
struct node {
int x;
int y;
int d;
}edge[M*5];
struct Node {
int len;
int ans;
int id;
}query[M];
int p[M];
int sum[M];
int n, m, q;
bool cmp(node p1, node p2) {
return p1.d < p2.d;
}
bool cmp1(Node p1, Node p2) {
return p1.len < p2.len;
}
bool cmp2(Node p1, Node p2) {
return p1.id < p2.id;
}
void init() {
for(int i = 1; i <= n; i++) {
p[i] = i;
sum[i] = 1;
}
}
int Find(int a) {
return a == p[a] ? a : p[a] = Find(p[a]);
}
int Union(int a, int b) {
a = Find(a);
b = Find(b);
if(a == b)
return 0;
else {
p[a] = b;
int temp = sum[a]*sum[b];
sum[b] += sum[a];
return temp;
}
}
int main()
{
while(scanf("%d%d%d", &n, &m, &q) != EOF) {
init();
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].d);
}
for(int i = 0; i < q; i++) {
scanf("%d", &query[i].len);
query[i].id = i;
query[i].ans = 0;
}
sort(edge, edge+ m, cmp);
sort(query, query+q, cmp1);
int cnt = 0;
for(int i = 0; i < q; i++) {
while(edge[cnt].d <= query[i].len && cnt < m) {
query[i].ans += Union(edge[cnt].x, edge[cnt].y);
cnt++;
}
if(i > 0)
query[i].ans += query[i-1].ans;
}
sort(query, query+q, cmp2);
for(int i = 0; i < q; i++) {
printf("%d
", query[i].ans);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2236 Wireless Network 간편한 검색 및 수집The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftersho...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.