POJ3723 Conscription Kruskal算法并查集

妖狐艹你老母 2023-07-11 12:48 86阅读 0赞

[题目链接][Link 1]

# Conscription #

Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 21271 Accepted: 7311

### Description ###

Windy has a country, and he wants to build an army to protect his country. He has picked up N girls and M boys and wants to collect them to be his soldiers. To collect a soldier without any privilege, he must pay 10000 RMB. There are some relationships between girls and boys and Windy can use these relationships to reduce his cost. If girl x and boy y have a relationship d and one of them has been collected, Windy can collect the other one with 10000-d RMB. Now given all the relationships between girls and boys, your assignment is to find the least amount of money Windy has to pay. Notice that only one relationship can be used when collecting one soldier.

### Input ###

The first line of input is the number of test case.  
The first line of each test case contains three integers, N, M and R.  
Then R lines followed, each contains three integers xi, yi and di.  
There is a blank line before each test case.

1 ≤ N, M ≤ 10000  
0 ≤ R ≤ 50,000  
0 ≤ xi < N  
0 ≤ yi < M  
0 < di < 10000

### Output ###

For each test case output the answer in a single line.  
Sample Input

5 5 8  
4 3 6831  
1 3 4583  
0 0 6592  
0 1 3063  
3 3 4975  
1 3 2049  
4 2 2104  
2 2 781

5 5 10  
2 4 9820  
3 2 6236  
3 1 8864  
2 4 8326  
2 0 5156  
2 0 1463  
4 1 2439  
0 4 4373  
3 4 8889  
2 4 3133

#### Sample Output ####

71071  
54223

#### Source ####

POJ Monthly Contest – 2009.04.05, windy7926778

这道题，其实很简单 ，先将边按大小排序，从大到小选取不冲突的边，求权值之和，所得权值之和即为最多可以节省的钱数，用总花费 - 节省 = ans.

这里朴素的实现了并查集，但过此题完全没有问题，毕竟这道题主要的时间复杂度，还是在于排序的花费，并且没有那种专门针对并查集的数据，并查集退化的影响不大。

# AC代码 #

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    const int max_N = 1e4;
    const int max_M = 1e4;
    const int max_R = 5e4;
    const int max_d = 9999;
    
    int N,M,R;
    
    struct edge
    {
        
        int x,y,z;
    };
    
    edge e[max_R];
    
    bool cmp(const edge &e1,const edge &e2)
    {
        
        return e1.z>e2.z;
    }
    
    // 并查集的实现
    int fa[max_N + max_M];
    // 初始化并查集
    void init()
    {
        
        for(int i=0;i<N+M;++i)
        {
        
            fa[i]=i;
        }
    }
    
    int Find(int x)
    {
        
        if(x==fa[x])
        {
        
            return x;
        }
        return fa[x]=Find(fa[x]);
    }
    
    bool same(int x,int y)
    {
        
        return Find(x)==Find(y);
    }
    
    void unite(int x,int y)
    {
        
        x=Find(x);
        y=Find(y);
    
        fa[x]=y;
    }
    
    void Kruskal()
    {
        
        init();
        sort(e,e+R,cmp);
    
    
        int total_relationship=0;
        for(int i=0;i<R;++i)
        {
        
            if(!same(e[i].x,e[i].y+N))
            {
        
                unite(e[i].x,e[i].y+N);
                //printf(" [%d] ",e[i].z);
                total_relationship += e[i].z;
            }
        }
        int ans=(N+M)*10000 - total_relationship;
        printf("%d\n",ans);
    }
    
    int main()
    {
        
        int T;
        scanf("%d",&T);
        while(T--)
        {
        
            scanf("%d %d %d",&N,&M,&R);
            for(int i=0;i<R;++i)
            {
        
                scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].z);
            }
            Kruskal();
        }
        return 0;
    }

上面呢，只是为了节省时间，为了保险起见，我们加上秩，对并查集进行一个小优化。

## 优化并查集的AC代码 ##

#include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    const int max_N = 1e4;
    const int max_M = 1e4;
    const int max_R = 5e4;
    const int max_d = 9999;
    
    int N,M,R;
    
    struct edge
    {
        
        int x,y,z;
    };
    
    edge e[max_R];
    
    bool cmp(const edge &e1,const edge &e2)
    {
        
        return e1.z>e2.z;
    }
    
    // 并查集的实现
    int fa[max_N + max_M];
    int Rank[max_N + max_M];
    // 初始化并查集
    void init()
    {
        
        for(int i=0;i<N+M;++i)
        {
        
            fa[i]=i;
            Rank[i]=0;
        }
    }
    
    int Find(int x)
    {
        
        if(x==fa[x])
        {
        
            return x;
        }
        return fa[x]=Find(fa[x]);
    }
    
    bool same(int x,int y)
    {
        
        return Find(x)==Find(y);
    }
    
    void unite(int x,int y)
    {
        
        x=Find(x);
        y=Find(y);
    
        if(x==y)
        {
        
            return;
        }
    
        if(Rank[x]<Rank[y])
        {
        
            fa[x]=y;
        }
        else
        {
        
            fa[y]=x;
            if(Rank[x]==Rank[y])
            {
        
                ++Rank[x];
            }
        }
    }
    
    void Kruskal()
    {
        
        init();
        sort(e,e+R,cmp);
    
    
        int total_relationship=0;
        for(int i=0;i<R;++i)
        {
        
            if(!same(e[i].x,e[i].y+N))
            {
        
                unite(e[i].x,e[i].y+N);
                //printf(" [%d] ",e[i].z);
                total_relationship += e[i].z;
            }
        }
        int ans=(N+M)*10000 - total_relationship;
        printf("%d\n",ans);
    }
    
    int main()
    {
        
        int T;
        scanf("%d",&T);
        while(T--)
        {
        
            scanf("%d %d %d",&N,&M,&R);
            for(int i=0;i<R;++i)
            {
        
                scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].z);
            }
            Kruskal();
        }
        return 0;
    }

来看看两种代码执行的结果。

![20200305205226848.png][]

看起来时间上基本一样，都在0.4秒时间完成，对于1秒的时间限制，完全够用了。

再看空间，当然优化并查集花费的略多一些，但是800+K的内存，对于64MB的内存限制，完全不成问题。

综上，可以在某些并查集做辅助而非主要开销的程序中，为了节省篇幅可以使用朴素的并查集。  
**注意**，这里的朴素并非很朴素，路径压缩还是很容易实现的，也是必须的，这样才能保证大量重复查询中，并查集的效率。

当然，在某些专门针对并查集的题目中，还是要使用待优化的并查集的。

[Link 1]: http://poj.org/problem?id=3723
[20200305205226848.png]: https://img-blog.csdnimg.cn/20200305205226848.png