华师一附中OI组

标题: P2078 朋友 [打印本页]
作者: admin    时间: 2018-7-27 22:44
标题: P2078 朋友
题目背景
小明在A公司工作，小红在B公司工作。
https://www.luogu.org/problemnew/show/P2078


题目描述
这两个公司的员工有一个特点：一个公司的员工都是同性。

A公司有N名员工，其中有P对朋友关系。B公司有M名员工，其中有Q对朋友关系。朋友的朋友一定还是朋友。

每对朋友关系用两个整数(Xi,Yi)组成，表示朋友的编号分别为Xi，Yi。男人的编号是正数，女人的编号是负数。小明的编号是1，小红的编号是-1.

大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入输出格式
输入格式：
第1行，4个空格隔开的正整数N,M,P,Q。

之后P行，每行两个正整数Xi，Yi。

之后Q行，每行两个负整数Xi，Yi。

输出格式：
一行，一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣。（包括他们自己）

输入输出样例
输入样例#1：
4 3 4 2
1 1
1 2
2 3
1 3
-1 -2
-3 -3
输出样例#1：
2
说明
对于30%数据，N,M<=100，P,Q<=200

对于80%数据，N,M<=4000,P,Q<=10000.

对于全部数据，N,M<=10000,P,Q<=20000。

作者: 吴语林    时间: 2018-7-28 07:46
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <map>
  6. #include <string>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. using namespace std;
  13. int fa[55000],p,q,x,y,n,m,all1=0,all2=0;
  14. int getf(int u)
  15. {
  16.         if(fa[u]==u)
  17.                 return u;
  18.         int temp=getf(fa[u]);
  19.         fa[u]=temp;
  20.         return temp;
  21. }
  22. int main()
  23. {  
  24.         scanf("%d%d%d%d",&n,&m,&p,&q);
  25.         for(int i=1;i<=n+m;i++)
  26.                 fa[i]=i;
  27.         for(int i=1;i<=p;i++)
  28.         {
  29.                 scanf("%d%d",&x,&y);
  30.                 int t1=getf(x),t2=getf(y);
  31.                 if(t1!=t2)
  32.                         fa[t1]=t2;
  33.         }
  34.         for(int i=1;i<=q;i++)
  35.         {
  36.                 scanf("%d%d",&x,&y);
  37.                 int t1=getf(n-x),t2=getf(n-y);
  38.                 if(t1!=t2)
  39.                         fa[t1]=t2;
  40.         }
  41.         for(int i=1;i<=n;i++)
  42.                 if(getf(i)==getf(1))
  43.                         all1++;
  44.         for(int i=n+1;i<=n+m;i++)
  45.                 if(getf(i)==getf(n+1))
  46.                         all2++;
  47.         printf("%d",min(all1,all2));
  48.     return 0;
  49. }
复制代码
作者: 黄煦喆    时间: 2018-7-28 08:53
本帖最后由 黄煦喆 于 2018-7-28 09:10 编辑
  1. #include<iostream>
  2. using namespace std;
  3. int n,m,p,q,ans1,ans2;
  4. int par[20001];
  5. int f(int a)
  6. {
  7.     while(par[a]!=par[par[a]])par[a]=par[par[a]];
  8.     return par[a];
  9. }
  10. void merge(int a,int b)
  11. {
  12.     int r1=f(a);
  13.     int r2=f(b);
  14.     if(r1==r2)return;
  15.     else par[r1]=r2;
  16. }
  17. int main()
  18. {
  19.     cin>>n>>m>>p>>q;
  20.     for(int i=1;i<=n+m;i++)par[i]=i;
  21.     int x,y;
  22.     for(int i=1;i<=p;i++)
  23.     {
  24.         cin>>x>>y;
  25.         merge(x,y);
  26.     }
  27.     for(int i=1;i<=q;i++)
  28.     {
  29.         cin>>x>>y;
  30.         merge(-x+n,-y+n);
  31.     }
  32.      for(int i=1;i<=n;++i)
  33.      if(f(i)==f(1))
  34.       ans1++;
  35.     for(int i=n+1;i<=n+m;++i)
  36.      if(f(i)==f(n+1))
  37.       ans2++;
  38.     cout<<min(ans1,ans2);
  39.     return 0;
  40. }
复制代码
作者: walk_alone    时间: 2018-7-29 20:13
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <map>
  4. using namespace std;
  5. map<int,int> father;
  6. int getfather(int x)
  7. {
  8.         if(x==father[x])
  9.                 return x;
  10.         return father[x]=getfather(father[x]);
  11. }
  12. int main()
  13. {
  14.         int n,m,p,q,a,b,sum1=0,sum2=0;
  15.     scanf("%d%d%d%d",&n,&m,&p,&q);
  16.     for(int i=-m;i<=n;i++)
  17.                 father[i]=i;
  18.     for(int i=1;i<=p+q;i++)
  19.         {
  20.         scanf("%d%d",&a,&b);
  21.         father[getfather(a)]=getfather(b);
  22.         }
  23.     for(int i=-m;i<=-1;i++)
  24.                 if(getfather(i)==getfather(-1))
  25.                         sum1++;
  26.     for(int i=1;i<=n;i++)
  27.                 if(getfather(i)==getfather(1))
  28.                         sum2++;
  29.     printf("%d",min(sum1,sum2));
  30. }
复制代码
作者: 张笑宇    时间: 2018-7-30 10:22
  1. #include<iostream>
  2. using namespace std;
  3. int n,m,p,q;
  4. const int mx=10010;
  5. int par[mx][3],i;///par[mx][1]是男
  6. int getpar(int a,int x)
  7. {
  8.     ///找根节点
  9.     if (par[a][x]!=a)
  10.         par[a][x]=getpar(par[a][x],x);
  11.     return par[a][x];
  12. }
  13. void merge_(int a,int b,int x)
  14. {
  15.     ///合并a，b所在集合
  16.     par[getpar(a,x)][x]=getpar(b,x);
  17.     return;
  18. }
  19. int main()
  20. {
  21.     cin>>n>>m>>p>>q;
  22.     for (i=1; i<=n; i++) par[i][1]=i;
  23.     for (i=1; i<=m; i++) par[i][2]=i;
  24.     for (i=1; i<=p; i++)
  25.     {
  26.         int a,b;
  27.         cin>>a>>b;
  28.         merge_(a,b,1);
  29.     }
  30.     for (i=1; i<=q; i++)
  31.     {
  32.         int a,b;
  33.         cin>>a>>b;
  34.         a=-a,b=-b;
  35.         merge_(a,b,2);
  36.     }
  37.     int ansa=0,ansb=0;
  38.     for (i=1; i<=n; i++)
  39.         if (getpar(i,1)==getpar(1,1)) ansa++;
  40.     for (i=1; i<=m; i++)
  41.         if (getpar(i,2)==getpar(1,2)) ansb++;
  42.     cout<<min(ansa,ansb);
  43.     return 0;
  44. }
复制代码
作者: ZMQ    时间: 2018-8-6 21:56
提示: 作者被禁止或删除 内容自动屏蔽



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2