Morris' Blog

2011-06-28 22:46:40Morris

a073. POJ2832 How Many Pairs?

留言 0 收藏 0 推薦 0

內容：

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.

輸入說明：

The first line of input contains three integer N, M and Q (1 < N ≤ 100,000, 0 < M ≤ 200,000, 0 < Q ≤ 200,000). N is the number of vertices, M is the number of edges and Q is the number of queries. Each of the next M lines contains three integers a, b, and c (1 ≤ a, b ≤ N, 0 ≤ c < 10⁸) describing an edge connecting the vertices a and b with length c. Each of the following Q lines gives a query consisting of a single integer A (0 ≤ A < 10⁸).

輸出說明：

Output the answer to each query on a separate line.

範例輸入：

範例輸出：

提示：

原题范围是

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);
    }
}

上一篇：a168. 3901 - Editor

下一篇：[C/C++][作業] "Digital" 字型，輸出大寫英文&數字&大小控制

Morris' Blog

a073. POJ2832 How Many Pairs?

你可能感興趣的文章

最後第82天

《荒蕪之地，應許之心》：在荒涼的人心找尋溫柔的沃土

彥五郎事件簿二百零四:稻草

喝白糖水

什麼是幸福