題目鏈接：
codeforces 277A - Learning Languages
題目描述：
一個團體有n個人，每個人都掌握了一些語言，每個人學一門語言有1個花費，兩個人之間可以通過其他人的翻譯，問最少花費多少使得這個團體的任意兩個人都可以交流？
解題思路：
可以bfs，dfs求連通塊，也可以用并查集求集合數目。(PS:唯一要注意的是當每一個人都是只會0種語言，辣么每個人是不是都要學習語言，特判一下就好辣)
?搜索專題，先貼dfs代碼咯~
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 205; 4 struct Edge//鄰接表建圖，dfs求連通塊數目 5 { 6 int to, next; 7 }; 8 9 Edge edge[maxn*maxn]; 10 int head[maxn], vis[maxn], tot; 11 12 void Add (int from, int to) 13 { 14 edge[tot].to = to; 15 edge[tot].next = head[from]; 16 head[from] = tot ++; 17 } 18 void dfs (int x) 19 { 20 vis[x] = 1; 21 for (int i=head[x]; i!=-1; i=edge[i].next) 22 if (!vis[edge[i].to]) 23 dfs (edge[i].to); 24 } 25 26 int main () 27 { 28 int n, m; 29 while (scanf ("%d %d", &n, &m) != EOF) 30 { 31 int k, num, sum = 0; 32 tot = 0; 33 memset (head, -1, sizeof(head)); 34 memset (edge, 0, sizeof(edge)); 35 memset (vis, 0, sizeof(vis)); 36 for (int i=0; i<n; i++) 37 { 38 scanf ("%d", &k); 39 sum += k; 40 while (k --) 41 { 42 scanf ("%d", &num); 43 Add (i, num+n-1); 44 Add (num+n-1, i); 45 } 46 } 47 num = 0; 48 for (int i=0; i<n; i++) 49 if (!vis[i]) 50 { 51 dfs(i); 52 num ++; 53 } 54 if (sum) 55 num --; 56 printf ("%d\n", num); 57 } 58 return 0; 59 }
?
再貼一個并查集代碼
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 205; 4 int father[maxn], n, m; 5 6 void init () 7 { 8 for (int i=0; i<maxn; i++) 9 father[i] = i; 10 } 11 int find (int x) 12 { 13 if (father[x] != x) 14 father[x] = find (father[x]); 15 return father[x]; 16 } 17 int main () 18 { 19 while (scanf ("%d %d", &n, &m) != EOF) 20 { 21 init (); 22 int k, x, ans = 0; 23 for (int i=1; i<=n; i++) 24 { 25 scanf ("%d", &k); 26 if (k) 27 ans = -1; 28 while (k --) 29 { 30 scanf ("%d", &x); 31 int pi = find(i); 32 int px = find(x+n); 33 if (pi != px) 34 father[px] = father[pi]; 35 } 36 } 37 for (int i=1; i<=n; i++) 38 if (father[i] == i) 39 ans ++; 40 printf ("%d\n", ans); 41 } 42 return 0; 43 }
?—————————————————————————————————————我是華麗的分割線——————————————————————————————————
題目鏈接：
codeforce 520B - Two Buttons
題目描述：
有n,m兩個數，現有兩種操作：
1：n可以*2；2：n可以減1。問最少操作多少次可以使n==m？
解題思路：
這次是最優解，又是搜索專題，肯定是bfs咯，tle的估計就是vis數組出問題咯，還有要注意n,m的范圍喲！
還是先貼bfs代碼
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 10005; 4 struct node 5 { 6 int x, step; 7 }; 8 int bfs (int n, int m) 9 { 10 node p, q; 11 queue <node> Q; 12 int vis[maxn]; 13 memset (vis, 0, sizeof(vis)); 14 vis[n] = 1; 15 p.x = n; 16 p.step = 0; 17 Q.push (p); 18 while (!Q.empty()) 19 { 20 p = Q.front(); 21 Q.pop(); 22 if (p.x == m) 23 return p.step; 24 q.step = p.step + 1; 25 int x = p.x - 1; 26 int y = p.x * 2; 27 if (x > 0 && !vis[x]) 28 { 29 q.x = x; 30 Q.push (q); 31 vis[x] = 1; 32 } 33 if (p.x<m && y<maxn && !vis[y]) 34 { 35 q.x = y; 36 Q.push (q); 37 vis[y] = 1; 38 } 39 } 40 } 41 int main () 42 { 43 int n, m; 44 while (scanf ("%d %d", &n, &m) != EOF) 45 printf ("%d\n", bfs(n, m)); 46 return 0; 47 }
再貼一個代碼，這個代碼簡單易懂
1 /*這個要進行逆向思維 2 這時候要考慮把m-->n 3 兩種操作就變成了m/2與m+1 4 當m>n的時候只能進行+1操作 5 當m<n的時候只能進行/2操作(要討論m的奇偶性) 6 循環操作，m==n的時候就一切ok啦 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 const int maxn = 10005; 11 int main () 12 { 13 int n, m, ans; 14 while (scanf ("%d %d", &n, &m) != EOF) 15 { 16 ans = 0; 17 while (true) 18 { 19 if (m <= n) 20 { 21 ans += n - m; 22 break; 23 } 24 if (m%2) 25 { 26 m ++; 27 ans ++; 28 } 29 m /= 2; 30 ans ++; 31 } 32 printf ("%d\n", ans); 33 } 34 return 0; 35 }
這兩個題目都可以用其他方法做，完美的避開了搜索，不知道會不會對小學弟（美）們造成誤導哦，還是聲明一下搜索很重要的，搜索很重要的，搜索很重要的（重要的事情說三遍）。是很多其他算法的基礎。
?
————————————————————————————————————我是邪魅溫柔的分割線——————————————————————————————
?
題目鏈接：
Codeforces 445B -?DZY Loves Chemistry
題目描述：
n種試劑，m種反應(反應發生在兩種試劑之間)，DZY想要把這n種試劑混合，DZY依次向試管中加入試劑，剛開始試管的危險系數為1，如果當前所需要加入的試劑能與試管中的某種試劑反應，則試管的危險系數乘二，現在為了安全起見，問試管最高的危險系數是多少？
解題思路：
很裸地并查集嘛！因為最終的狀態肯定是所有的試劑都在試管里面，只需要知道每個集合里面元素個數就OK啦！！
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 typedef __int64 LL; 8 const int maxn = 100; 9 int father[maxn]; 10 void init () 11 { 12 for (int i=0; i<maxn; i++) 13 father[i] = i; 14 } 15 int Find(int x) 16 { 17 if (x != father[x]) 18 father[x] = Find(father[x]); 19 return father[x]; 20 } 21 int main () 22 { 23 int n, m; 24 while (scanf ("%d %d", &n, &m) != EOF) 25 { 26 init (); 27 LL ans = 1; 28 while (m --) 29 { 30 int x, y; 31 scanf ("%d %d", &x, &y); 32 int px = Find (x); 33 int py = Find (y); 34 if (px != py) 35 { 36 father[px] = py; 37 ans *= 2; 38 } 39 } 40 printf ("%I64d\n", ans); 41 } 42 return 0; 43 }
?
