CF277A Learning Languages 解题报告_综合

CF277A Learning Languages 解题报告

1 题目链接

https://codeforces.com/problemset/problem/277/A

2 题目整理

题目：学习语言

题目描述

BerCorp公司有 $n$ 名员工。这些员工可以使用经批准的官方语言进行正式通信。语言用从 $1$ 到 $m$ 的整数进行编号。对于每个员工，我们都有他所知道的语言列表。这个列表可以是空的，即员工可能不懂官方语言。但员工愿意学习任何官方语言，只要公司支付他们的课程。一名员工参加一种语言的学习课程的费用是 $1$ 美元。

找出公司需要花费的最低金额，这样任何员工都可以与其他员工通信(他们的通信可以是间接的，也就是说，其他员工可以帮助翻译)。

输入格式

第一行两个整数 $n, m$ ，分别表示员工的数量与官方语言的种类数。

接下来 $n$ 行每行第一个整数是 $k_i$ ，表示第 $i$ 位员工的已学语言的种类数。接下来有 $k_i$ 个整数，第 $j$ 个整数 $a_{i,j}$ 表示第 $i$ 位员工第 $j$ 个已会语言的编号。

输出格式

一行一个整数，表示公司想让任意两个员工可以交流所需要的最小花费。

样例输入1

样例输出1

样例输入2

样例输出2

样例输入3

2 2
1 2
0

样例输出3

数据范围

对于 $100\%$ 的数据:

$\leq n, m \leq 100$
$\leq k_i \leq m$
$\leq a_{i,j} \leq m$

3 题意分析

3.1 题目大意

有 $n$ 个人， $m$ 种语言，每个人会 $k_i$ 种语言，有相同语言的可以直接沟通。现在问至少要让一些人多学几种语言，才能使所有人能自由交谈。

3.2 样例分析

如上所述。

4 解法分析

一道普通的建图+并查集的简单题目。

首先，因为会相同语言的两个人可以直接沟通，所以把这两个人连起来。按照这样的规则用并查集建图，最后会有 $p$ 个连通块。如果其中有一个人会一种语言以上，那么答案为 $p ? 1$ ,就是让其他人都学这种语言；否则答案为 $p$ ，就是所有人都学一种语言。

AC代码

ACCode #001

// From Heart_Blue
// Rating 2425
// reason : 思路清晰代码简洁明了，运用了Class + 并查集
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e2 + 10;
int flag[N];
class UnionFind
{
    
private:int p[N];
public:int size(int x){
    int px = Find(x);return -p[px];}void init(){
    MEM(p, -1);}int Find(int x){
    int root = x;while (p[root] >= 0) root = p[root];while (x != root){
    int tmp = p[x];p[x] = root;x = tmp;}return root;}void Union(int x, int y){
    int px = Find(x);int py = Find(y);if (size(px) > size(py)) swap(px, py);int total = size(px) + size(py);p[px] = py;p[py] = -total;}
} uf;
int main()
{
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);uf.init();MEM(flag, 0);int n, m;cin >> n >> m;int f = 0;for (int i = 1; i <= n; i++){
    int tot;cin >> tot;if (tot > 0) f = 1;while (tot--){
    int x;cin >> x;if (uf.Find(x + n) != uf.Find(i)){
    uf.Union(x + n, i);}}}int ans = 0;for (int i = 1; i <= n; i++){
    int fa = uf.Find(i);if (!flag[fa]) ans++;flag[fa] = 1;}cout << ans - f << endl;return 0;
}

ACCode #002

// From snuke
// Rating 3099
// reason : 思路清晰代码简洁明了，运用了并查集
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<string.h>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<map>
#include<set>
#include<bitset>
#include<iostream>
#include<sstream>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
#define drep(i,n) for(int i = n-1; i >= 0; i--)
#define each(c,it) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y);
#define mins(x,y) x = min(x,y);
#define pb push_back
#define snuke srand((unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;const int MX = 105, INF = 1000000000, mod = 1000000009;
const ll LINF = 1000000000000000000ll;
const int dx[4] = {
    0,-1,1,0}, dy[4] = {
    -1,0,0,1};// Union find
struct uf{
    vector<int> par, rank;uf(){
    }uf(int sz){
     par.resize(sz); rank.resize(sz); init(sz);}void init(int sz){
     rep(i,sz) par[i] = i, rank[i] = 1;}int pa(int x){
    if(par[x] == x) return x;return par[x] = pa(par[x]);}void uni(int x, int y){
    x = pa(x); y = pa(y);if(rank[x] < rank[y]) swap(x,y);par[y] = x;if(rank[x] == rank[y]) rank[x]++;}
};
//int l[MX]; bool b[MX];int main(){
    int n, m, k, ans = 0;scanf("%d%d",&n,&m);uf t(m+1);rrep(i,m) b[i] = false;rep(i,n){
    scanf("%d",&k);rep(j,k){
    scanf("%d",&l[j]);rep(h,j) t.uni(l[j],l[h]);b[l[j]] = true;}if(k == 0) ans++;}bool bl = false;rrep(i,m){
    if(b[i] && t.pa(i) == i){
    if(bl) ans++;bl = true;}}printf("%d\n",ans);return 0;
}

ACCode #003

// From rng_58
// Rating 3074
// reason : 思路清晰代码简洁明了，运用了并查集
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>using namespace std;#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)#define MAXV 110int parent[MAXV],rank[MAXV];void init(int n){
    int i;REP(i,n) {
    parent[i] = i; rank[i] = 1;}
}int root(int x){
    if(parent[x] != x) parent[x] = root(parent[x]);return parent[x];
}void connect(int x, int y){
    int rx=root(x),ry=root(y);if(rx == ry) return;if(rank[rx] > rank[ry]) {
    parent[ry] = rx; rank[rx] += rank[ry];}if(rank[rx] <= rank[ry]) {
    parent[rx] = ry; rank[ry] += rank[rx];}
}bool a[110][110];int main(void){
    int N,M,K,i,j,k,x;cin >> N >> M;REP(i,N){
    cin >> K;REP(j,K){
    cin >> x;a[i][x-1] = true;}}bool nonzero = false;REP(i,N) REP(j,M) if(a[i][j]) nonzero = true;if(!nonzero){
    cout << N << endl;return 0;}init(N);REP(i,N) REP(j,N) if(i < j){
    bool found = false;REP(k,M) if(a[i][k] && a[j][k]) found = true;if(found){
    connect(i, j);// cout << i << ' ' << j << endl;}}int comp = 0;REP(i,N) if(root(i) == i) comp++;cout << comp - 1 << endl;return 0;
}