P1682

· · 题解

过家家

题目大意（自认为较为简单的理解方式）

有 n 个人打农药 ，共有 n 个英雄， 每个人都有一个自己的英雄库 ， 互为好友的可共享英雄 ， 每个人还拥有可买 k 个英雄的点券 ， 求一个人能用的英雄最少为多少（一个英雄打一局，所以英雄最少的玩家打完后就不开心了所以就结束对局了） 。

分析 ：

首先这题一看便知是并查集，但是怎么并 / 查 ， 是个问题，我是一上来便直接硬上带权并查集然而在并的时候就发现英雄重叠不好处理，所以立刻陷入沉思。为避免英雄重复所以每个人和英雄并查集不能通用，所以我们便用并查集维护好友，先将每个人的英雄离线下来，在后面合并好友后，在开个桶打个标记将英雄都加到并查集联通快的代表节点（祖宗）上，标记防止算重，最后对于每个桶枚举找最小值 ，因为 k 自己能买的英雄量是固定的但总共只有 n 个英雄所以最后统计答案为 min(minn+k , n) 。

代码如下

#warning by StarMaster
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std ;

const int MM = 10000 ;
int n , fa[MM * 10]  , m , k , minn = 1e6 , f , num[MM * 10] ;
bool vis[MM][MM] ;

struct node
{
    int x , y ;
}a[MM * 10] ;

inline int min(int a , int b)
{
    return a < b ? a : b ;
}

inline int read()
{
    int x = 0 , f = 1 ;
    char ch = getchar() ;
    while(ch > '9' or ch < '0')
    {
        if(ch == '-') f = -1 ;
        ch = getchar() ;
    }
    while(ch >= '0' and ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48) ;
        ch = getchar() ;
    }
    return x * f ;
}

inline int Find(int x)
{
    if(x == fa[x]) return x ;
    else return fa[x] = Find(fa[x]) ;
}

int main()
{
    n = read() , m = read() , k = read() , f = read() ;
    for(int i = 1 ; i <= n ; i ++)
    {
        fa[i] = i ;
    }
    for(int i = 1 ; i <= m ; i ++)
    {
        a[i].x = read() , a[i].y = read() ;
    }
    for(int i = 1 ; i <= f ; i ++)
    {
        int x = read() , y = read() ;
        fa[Find(x)] = Find(y) ;
    }
    for(int i = 1 ; i <= m ; i ++)
    {
        if(!vis[Find(a[i].x)][a[i].y])
        {
            num[Find(a[i].x)] ++ ;//累加祖宗节点英雄量
            vis[Find(a[i].x)][a[i].y] = 1 ;//标记防止算重
        }
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(num[i]) minn = min(minn , num[i]) ;//找最小值
    }
    cout << min(minn + k , n) ;//最小值加 k，与 n 取 min
    return 0 ;
}

完结撒花( ^ ▽ ^ )