[关闭]
@Alpacadh 2019-01-30T09:10:34.000000Z 字数 3373 阅读 747

ACM


J-并查集(Wireless Network POJ-2236)

题意:

解题思路:

代码:

  1. //#include<bits/stdc++.h>//因为POJ不支持万能表头 所以只能注释掉自己打所需要的函数库
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<stdio.h>
  7. #include<string.h>
  8. using namespace std;
  9. const int inf=0x3f3f3f3f;
  10. const int N=1e4+5;
  11. const double eps=1e-4;
  12. int fa[N];
  13. void init(int n)//初始化fa数组
  14. {
  15. for(int i=1;i<=n;i++)
  16. fa[i]=i;
  17. }
  18. int findd(int x)
  19. {
  20. if(x==fa[x])
  21. return x;
  22. else
  23. {
  24. return fa[x]=findd(fa[x]);
  25. }
  26. }
  27. bool Union(int x,int y)
  28. {
  29. int fx=findd(x),fy=findd(y);
  30. if(fx==fy)
  31. return false;
  32. else
  33. {
  34. fa[fx]=fy;
  35. return true;
  36. }
  37. }
  38. struct point
  39. {
  40. int x,y;
  41. }p[N];
  42. int k;
  43. int check(int a,int b)
  44. {
  45. return hypot(p[a].x-p[b].x,p[a].y-p[b].y)<=k;//hypot(a,b)返回的是以a,b为边的三角形的腰长,所以根据勾股定理这里可以用来算两点距离,但注意返回的是类型double。
  46. }
  47. int vis[N];
  48. int main()
  49. {
  50. int n;
  51. scanf("%d%d",&n,&k);
  52. for(int i=1;i<=n;i++)
  53. scanf("%d%d",&p[i].x,&p[i].y);
  54. char s[2];
  55. init(n);
  56. while(~scanf("%s",s))
  57. {
  58. int a,b;
  59. if(s[0]=='O')
  60. {
  61. scanf("%d",&a);
  62. vis[a]=1;
  63. for(int i=1;i<=n;i++)
  64. {
  65. if(vis[i]==1&&a!=i&&check(a,i))//判断是否被修复,该点不能是自身,与它相距小于D
  66. {
  67. Union(a,i);
  68. }
  69. }
  70. }
  71. else
  72. {
  73. scanf("%d%d",&a,&b);
  74. if(findd(a)==findd(b))
  75. printf("SUCCESS\n");
  76. else
  77. printf("FAIL\n");
  78. }
  79. }
  80. return 0;
  81. }

K-并查集(Ubiquitous Religions POJ-2524)

题意:

解题思路:

代码:

  1. //#include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<stdio.h>
  7. #include<string.h>
  8. using namespace std;
  9. const int inf=0x3f3f3f3f;
  10. const int N=5e4+5;
  11. const double eps=1e-4;
  12. int fa[N];
  13. void init(int n)
  14. {
  15. for(int i=1;i<=n;i++)
  16. fa[i]=i;
  17. }
  18. int findd(int x)
  19. {
  20. if(x==fa[x])
  21. return x;
  22. else
  23. {
  24. return fa[x]=findd(fa[x]);
  25. }
  26. }
  27. bool Union(int x,int y)
  28. {
  29. int fx=findd(x),fy=findd(y);
  30. if(fx==fy)
  31. return false;
  32. else
  33. {
  34. fa[fx]=fy;
  35. return true;
  36. }
  37. }
  38. int main()
  39. {
  40. int cas=1;
  41. int n,m;
  42. while(~scanf("%d%d",&n,&m))//注意多组输入
  43. {
  44. if(n==0&&m==0)//终止输入的条件
  45. break;
  46. init(n);
  47. for(int i=0;i<m;i++)
  48. {
  49. int a,b;
  50. scanf("%d%d",&a,&b);
  51. Union(a,b);
  52. }
  53. int ans=0;
  54. for(int i=0;i<n;i++)
  55. {
  56. if(fa[i]==i)//判断他当前信仰的宗教是否与原来的相同
  57. ans++;
  58. }
  59. printf("Case %d: %d\n",cas++,ans);//注意输出不要漏掉Case
  60. }
  61. return 0;
  62. }

L-并查集(A Bug`s Life POJ-2492)

题意:

解题思路:

代码:

  1. //#include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<stdio.h>
  7. #include<string.h>
  8. using namespace std;
  9. const int inf=0x3f3f3f3f;
  10. const int N=2e4+5;
  11. const double eps=1e-4;
  12. int fa[N];
  13. void init(int n)
  14. {
  15. for(int i=1;i<=n;i++)
  16. fa[i]=i;
  17. }
  18. int findd(int x)
  19. {
  20. if(x==fa[x])
  21. return x;
  22. else
  23. {
  24. return fa[x]=findd(fa[x]);
  25. }
  26. }
  27. bool Union(int x,int y)
  28. {
  29. int fx=findd(x),fy=findd(y);
  30. if(fx==fy)
  31. return false;
  32. else
  33. {
  34. fa[fx]=fy;
  35. return true;
  36. }
  37. }
  38. int main()
  39. {
  40. int cas=1;
  41. int t;
  42. scanf("%d",&t);
  43. while(t--)
  44. {
  45. int n,m;
  46. scanf("%d%d",&n,&m);
  47. init(2*n);//注意因为有矛盾面的存在,所以fa数组要舒适化两倍。
  48. int vis=0;//标记
  49. for(int i=0;i<m;i++)
  50. {
  51. int a,b;
  52. scanf("%d%d",&a,&b);
  53. Union(a,b+n);//与对面矛盾面结合
  54. Union(b,a+n);
  55. if(findd(a)==findd(a+n)||findd(b)==findd(b+n))//判断是否与自己的矛盾面在相同集合
  56. {
  57. vis=1;
  58. }
  59. }
  60. printf("Scenario #%d:\n",cas++);
  61. if(vis==1)
  62. printf("Suspicious bugs found!\n");
  63. else
  64. printf("No suspicious bugs found!\n");
  65. printf("\n");
  66. }
  67. return 0;
  68. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注