首页 > ACM题库 > HDU-杭电 > hdu 2676 Circle-并查集-[解题报告]C++
2014
02-12

hdu 2676 Circle-并查集-[解题报告]C++

Circle

问题描述 :

There are n citys connecting by rivers. They form a circle as the picture showing.

Half of the citys will send a number of goods to another city by the river, so the other half of city will receive the goods. A city can send the goods by river clockwise or counterclockwise, but the numbers of goods can not change. How to transport let the largest number of goods in the rivers to minimize.
For example n = 4. the city 1 will send 4 goods to the city 3 and the city 2 will send 4 goods to the city 4. Pictures below show the two kinds of methods.

Method 1.
[1->2] = 4 + 2 = 6;
[2->3] = 4 + 2 = 6;
[3->4] = 0 + 2 = 2;
[4->1] = 0 + 2 = 2;
Max = [1->2] = 6;


Method 2.
[1->2] = 2 + 2 = 4;
[2->3] = 2 + 2 = 4;
[3->4] = 2 + 2 = 4;
[4->1] = 2 + 2 = 4;
Max = [1->2] = 4;

So the Method 2 is better than Method 1.

输入:

The input contains multiple test cases.
Each case first given a even integer n (2 <= n <= 1000)
Than n/2 lines,each line have three integer A,B,c standing the city A will send c goods to the city B;(1<=A<B<=n, 0<c<=10)

输出:

The input contains multiple test cases.
Each case first given a even integer n (2 <= n <= 1000)
Than n/2 lines,each line have three integer A,B,c standing the city A will send c goods to the city B;(1<=A<B<=n, 0<c<=10)

样例输入:

4
1 3 4
2 4 4
2
1 2 5

样例输出:

4
3

#include<iostream>
#include<cstdio>
using namespace std;
int father[5005],num[5005];
int n,m,q;
void makeset(int n){
    for(int j=1;j<=n;j++){
        father[j]=j;
        num[j]=1;
    }
}
int findset(int x){
    return father[x]==x?x:father[x]=findset(father[x]);
}
void Union(int a,int b){
    int x=findset(a);
    int y=findset(b);
    if(x==y)
        return;
    if(num[x]<=num[y]){
        father[x]=y;
        num[y]+=num[x];
    }
    else{
        father[y]=x;
        num[x]+=num[y];
    }
}
int main(){
    int t=0;
    while(scanf("%d%d%d",&n,&m,&q)==3){
        makeset(n);
        int a,b;
        for(int i=0;i<m;i++){
            scanf("%d%d",&a,&b);
            Union(a,b);
        }
        for(int i=0;i<q;i++){
            scanf("%d%d",&a,&b);
            findset(a)==findset(b)?puts("yes"):puts("no");
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/jjaw2013/article/details/19125109


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks