Alex0319

分类

PAT(11) poj(16) 算法(1) 题解(30)

/ 注册

全部文章（共8篇）

poj2236 938ms 并查集

#include<cstdio> using namespace std; //把可以连通的放到一个集合，然后再判断两台机子是不是在一个集合 const int N = 1e4; int father[N+5]; bool vis[N+5]; int d; struct Node { ...

Union_Find poj

2019-08-30

0 532

poj1182 266ms 并查集

没有大佬那么厉害的可以直接得出结论，只能把情况都列出来，其实一共只有18种情况，所以不妨头脑风暴一次，然后稍加整理(先根据d的值分类，再根据rank[a]的值进行分类)规律就显然了。详细阐述下整理部分吧。首先把d=1，2，这是两种情况，然后细分，例如，当d=1，把rank[a],rank[b],ra...

Union_Find poj

2019-08-29

0 735

poj1988 266ms 并查集

#include<cstdio> using namespace std; //说难不难，说简单不简单，就是并查集的处理，额外的两个数组是关键 //解决并查集有关问题时，如何利用辅助数组记录节点与根节点的关系是解题的关键 const int N = 3e4; int father[N+5...

Union_Find poj

2019-08-28

0 553

poj1703 带权并查集344ms

include using namespace std;//带权并查集难点就是关系更新，其他的与普通并查集无异const int Maxn = 1e5;int rel[Maxn+5],father[Maxn+5];//0同1异void init(int n){ for(int i = 1; i...

Union_Find poj

2019-08-27

0 580

poj2492 750ms 解法二：带权并查集

#include<cstdio> using namespace std; const int Maxn = 2019; int rel[Maxn],father[Maxn]; //0表示同性，1表示异性 //参考网上的第二种解法，也就是带权(种类)并查集 void init(int n...

Union_Find poj

2019-08-27

0 574

poj2492 766ms 带权并查集

#include<cstdio> #include<cstring> using namespace std; //带权并查集其一解法 //敌人的敌人就是朋友 const int Maxn = 2000; int father[Maxn<<1]; void ini...

Union_Find poj

2019-08-26

0 451

pooj2524 313ms 并查集

规整一点，将各个步骤写成函数，所以函数调用浪费了时间 #include using namespace std; //union_find //水题，先把每人看成一个社团，然后合并一个，减一就好 int father[50005]; int ans; void init(int n) { f...

Union_Find poj

2019-08-25

1 590

poj1611 并查集基础 0ms

方法一： 16ms #include<cstdio> #define maxn 30000 using namespace std; int tree[maxn+5];//并查集的树 int sum[maxn+5];//嫌疑人数 void init(int n) //并查集的初始化 {...

poj Union_Find

2019-07-22

0 556