a073. POJ2832 How Many Pairs?
內容
：
You are given an undirected graph G with N vertices and M edges. Each edge has a length. Below are two definitions.
- Define max_len(p) as the length of the edge with the maximum length of p where p is an arbitrary non-empty path in G.
- Define min_pair(u, v) as min{max_len(p) | p is a path connecting the vertices u and v.}. If there is no paths connecting u and v, min_pair(u, v) is defined as infinity.
Your task is to count the number of (unordered) pairs of vertices u and v satisfying the condition that min_pair(u, v) is not greater than a given integer A.
輸入說明
：
輸出說明
：
Output the answer to each query on a separate line.
範例輸入
：
4 5 4
1 2 1
2 3 2
2 3 5
3 4 3
4 1 4
0
1
3
2
範例輸出
：
提示
：
原题范围是
1 < N ≤ 10,000, 0 < M ≤ 50,000, 0 < Q ≤ 10,000
这里改为
1 < N ≤ 100,000, 0 < M ≤ 200,000, 0 < Q ≤ 200,000
为了不让O(N^2)的过...
POJ 2832
这里，N个点的编号是1,2,3,4,5,....,N
出處
：
POJ Monthly--2006.05.28, zhucheng
(管理：
liouzhou_101)
作法 : 并查集
題目描述 : 給你一個圖形，問x->y的路徑上最小值w，詢問Qw,有多少對的(x,y)，符合w ≦Qw
將輸入給的w由小至大排序，開始將 x-y 串起來
保持Ans，若x所在的團，跟y所在的團不同，分別有 tx,ty個在其中
那麼，Ans = Ans - [(tx)*(tx-1)/2 + (ty)*(ty-1)/2] + (tx+ty)*(tx+ty-1)/2;
化簡 Ans = tx*ty;
所在的團，所有連通路徑值皆小於等於當前給予的 "邊大小"，因此彼此可以互相到達
因此由小至大更新，我們可以得知，當邊限制多少時，Ans 會等於多少
做了兩種版本，離線版本速度 > 線上版本速度
離線版本
/**********************************************************************************//* Problem: a073 "POJ2832 How Many Pairs?" from POJ Monthly--2006.05.28, zhucheng*//* Language: C *//* Result: AC (348ms, 9644KB) on ZeroJudge *//* Author: morris1028 at 2011-06-28 19:35:41 *//**********************************************************************************/#include<stdio.h>int Parent[100001], Rank[100001];long long Ans = 0;void MakeSet(int N) { int a; for(a = 0; a <= N; a++) Parent[a] = a, Rank[a] = 1; } int FindSet(int x) { if(x != Parent[x]) Parent[x] = FindSet(Parent[x]); return Parent[x];}void Link(int x, int y) { Ans += (Rank[x]*Rank[y]); if(Rank[x] > Rank[y]) Parent[y] = x, Rank[x] += Rank[y]; else Parent[x] = y, Rank[y] += Rank[x];} void Union(int x, int y) { x = FindSet(x), y = FindSet(y); if(x != y) Link(x, y);}typedef struct { int x, y, w;}link;link Map[200000], X[200000], query[200000];long long queryAns[200000];void MergeSort(int, int, link []);int Input() { char cha; unsigned int x = 0; while(cha = getchar()) if(cha != ' ' && cha != '\n') break; x = cha-48; while(cha = getchar()) { if(cha == ' ' || cha == '\n') break; x = x*10 + cha-48; } return x; }main() { int N, M, Q, a; while(scanf("%d %d %d", &N, &M, &Q) == 3) { MakeSet(N); for(a = 0; a < M; a++) Map[a].x = Input(), Map[a].y = Input(), Map[a].w = Input(); for(a = 0; a < Q; a++) query[a].w = Input(), query[a].y = a; MergeSort(0, M-1, Map); MergeSort(0, Q-1, query); int index = 0; Ans = 0; for(a = 0; a < Q; a++) { while(index < M && Map[index].w <= query[a].w) Union(Map[index].x, Map[index].y), index++; queryAns[query[a].y] = Ans; } for(a = 0; a < Q; a++) printf("%lld\n", queryAns[a]); } return 0;}void Merge(int l, int m, int r, link Data[]) { int In1 = l, In2 = m+1; int a, b, Top = 0; while(In1 <= m && In2 <= r) if(Data[In1].w <= Data[In2].w) X[Top++] = Data[In1++]; else X[Top++] = Data[In2++]; while(In1 <= m) X[Top++] = Data[In1++]; while(In2 <= r) X[Top++] = Data[In2++]; for(a = 0, b = l; a < Top; a++, b++) Data[b] = X[a];}void MergeSort(int l, int r, link Data[]) { if(l < r) { int m = (l+r)/2; MergeSort(l, m, Data); MergeSort(m+1, r, Data); Merge(l, m, r, Data); }}
線上版本 : 二分搜尋答案
/**********************************************************************************/
/* Problem: a073 "POJ2832 How Many Pairs?" from POJ Monthly--2006.05.28, zhucheng*/
/* Language: C */
/* Result: AC (368ms, 7296KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-28 20:23:37 */
/**********************************************************************************/
#include<stdio.h>
int Parent[100001], Rank[100001];
long long Ans = 0;
void MakeSet(int N) {
int a;
for(a = 0; a <= N; a++)
Parent[a] = a, Rank[a] = 1;
}
int FindSet(int x) {
int r = x, y = x;
while(r != Parent[r])
r = Parent[r];
while(x != Parent[x])
x = Parent[x], Parent[x] = r;
return r;
}
void Link(int x, int y) {
Ans += (Rank[x]*Rank[y]);
if(Rank[x] > Rank[y])
Parent[y] = x, Rank[x] += Rank[y];
else
Parent[x] = y, Rank[y] += Rank[x];
}
void Union(int x, int y) {
x = FindSet(x), y = FindSet(y);
if(x != y)
Link(x, y);
}
typedef struct {
long long x;
int y, w;
}link;
link Map[200000], X[200000];
void MergeSort(int, int, link []);
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n') break;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
long long search(int l, int r, int v) {
int m;
do {
m = (l + r)/2;
if(Map[m].w > v) r = m-1;
else {
if(m < r) {
if(Map[m+1].w > v)
return Map[m].x;
l = m + 1;
}
else return Map[m].x;
}
}while(l <= r);
return 0;
}
main() {
int N, M, Q, a;
while(scanf("%d %d %d", &N, &M, &Q) == 3) {
MakeSet(N);
for(a = 0; a < M; a++)
Map[a].x = Input(), Map[a].y = Input(), Map[a].w = Input();
Ans = 0, MergeSort(0, M-1, Map);
for(a = 0; a < M; a++)
Union((int)Map[a].x, Map[a].y), Map[a].x = Ans;
for(a = 0; a < Q; a++) {
N = Input();
printf("%lld\n", search(0, M-1, N));
}
}
return 0;
}
void Merge(int l, int m, int r, link Data[]) {
int In1 = l, In2 = m+1;
int a, b, Top = 0;
while(In1 <= m && In2 <= r)
if(Data[In1].w <= Data[In2].w)
X[Top++] = Data[In1++];
else
X[Top++] = Data[In2++];
while(In1 <= m) X[Top++] = Data[In1++];
while(In2 <= r) X[Top++] = Data[In2++];
for(a = 0, b = l; a < Top; a++, b++)
Data[b] = X[a];
}
void MergeSort(int l, int r, link Data[]) {
if(l < r) {
int m = (l+r)/2;
MergeSort(l, m, Data);
MergeSort(m+1, r, Data);
Merge(l, m, r, Data);
}
}
文章定位：
