BZOJ 3296 [USACO2011 Open] Learning Languages：并查集

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3296

题意：

　　农夫约翰的N（2 <= N <= 10,000）头奶牛，编号为1...N。

　　一共会流利地使用M（1<= M <=30,000）种语言，编号从1...M。

　　第i头，会说K_i（1 <= K_i <= M）种语言，即L_i1, L_i2,..., L_{iK_i} (1 <= L_ij <= M)。

　　FJ的奶牛不太聪明，所以K_i的总和至多为100,000。

　　两头牛，不能直接交流，除非它们都会讲某一门语言。然而，没有共同语言的奶牛们，可以让其它的牛给他们当翻译。换言之，牛A和B可以谈话，当且仅当存在一个序列奶牛T_1，T_2，...，T_k，A和T_1都会说某一种语言，T_1和T_2也都会说某一种语言...并且T_k和B会说某一种语言。

　　农夫约翰希望他的奶牛更加团结，所以他希望任意两头牛之间可以交流。他可以买书教他的奶牛任何语言。作为一个相当节俭的农民，FJ想要购买最少的书籍，让所有他的奶牛互相可以说话。

　　帮助他确定：他必须购买的书籍的最低数量。

题解：

　　并查集。

　　将所有有共同语言的牛合并。

　　因为当前所有的集合两两之间都没有共同语言，所以每买一本书，只能将其中两个集合合并。

　　所以：最后答案 = 集合个数 - 1

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #define MAX_N 10005

 #define MAX_M 30005

 using namespace std;

 int n,m;

 int ans=;

 int par[MAX_N];

 int lang[MAX_M];

 void init_union_find()

 {

     for(int i=;i<n;i++)

     {

         par[i]=i;

     }

 }

 int find(int x)

 {

     return par[x]==x?x:par[x]=find(par[x]);

 }

 void unite(int x,int y)

 {

     int px=find(x);

     int py=find(y);

     if(px==py) return;

     par[px]=py;

 }

 bool same(int x,int y)

 {

     return find(x)==find(y);

 }

 void read()

 {

     cin>>n>>m;

     init_union_find();

     memset(lang,-,sizeof(lang));

     int k,l;

     for(int i=;i<n;i++)

     {

         cin>>k;

         for(int j=;j<k;j++)

         {

             cin>>l;

             if(lang[l]!=-) unite(i,lang[l]);

             else lang[l]=i;

         }

     }

 }

 void solve()

 {

     for(int i=;i<n;i++)

     {

         if(find(i)==i) ans++;

     }

 }

 void print()

 {

     cout<<ans-<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

BZOJ 3296 [USACO2011 Open] Learning Languages：并查集

最新文章

热门文章