鄰接表的使用
鄰接表使用在什么時候呢？
想了想，覺得應該用來存儲樹。
還是來看一個例子吧。
題目：在一棵根樹上，Alice和Bob分別在其中某些結點上有一些大石頭。
現在Alice和Bob輪流移動屬于自己的石頭，移動的規則是這樣的，
選擇某個結點上的一塊石頭，將石頭移到該結點的父結點，當然，
位于根結點的石頭是不可移動的，因為根結點沒有父結點。Alice
先移動，當一方沒有石頭可移動的時候就輸了。
題解：只需計算每個石頭的移動次數，即所在結點在根樹中的深度即可。
現在我們已知的是根結點為0,那么我們我們可以用鄰接表來存儲，
可以從0號結點對遠向圖進行遍歷，可采用深度優先或廣度優先
來做。
深度優先代碼：
View Code
#include<stdio.h> #include<string.h> #define MAXN 10 int n, m1, m2; int degree[MAXN]; int list[MAXN][MAXN]; int dep[MAXN]; void DFS(int f, int u, int d){ dep[u] = d; for(int i=0; i<degree[u]; i++){ int v = list[u][i]; if(v==f) continue; DFS(u, v, d+1); } } int main(){ while(scanf("%d%d%d", &n, &m1, &m2)==3){ memset(degree, 0, sizeof(degree)); for(int i=1, x, y; i<n; i++){ scanf("%d%d", &x, &y); list[x][degree[x]++] = y; list[y][degree[y]++] = x; } DFS(-1, 0, 0); int f1, f2, u; f1 = f2 = 0; for(int i=0; i<m1; i++){ scanf("%d", &u); f1+=dep[u]; } for(int i=0; i<m2; i++){ scanf("%d", &u); f2+=dep[u]; } if(f1<=f2) printf("Bob\n"); else printf("Alice\n"); } }
廣度優先代碼：
View Code
#include<stdio.h> #include<string.h> #include<queue> #include<iostream> using namespace std; #define MAXN 10 int n, m1, m2; int degree[MAXN]; int list[MAXN][MAXN]; int dep[MAXN]; void BFS(){ queue<int> q; q.push(0); memset(dep, 0, sizeof(dep)); while(!q.empty()){ int u = q.front(); q.pop(); for(int i=0; i<degree[u]; i++){ int v = list[u][i]; if(v==0) continue; if(dep[v]!=0) continue; q.push(v); dep[v] = dep[u]+1; } } } int main(){ while(scanf("%d%d%d", &n, &m1, &m2)==3){ memset(degree, 0, sizeof(degree)); for(int i=1, x, y; i<n; i++){ scanf("%d%d", &x, &y); list[x][degree[x]++] = y; list[y][degree[y]++] = x; } BFS(); int f1, f2, u; f1 = f2 = 0; for(int i=0; i<m1; i++){ scanf("%d", &u); f1+=dep[u]; } for(int i=0; i<m2; i++){ scanf("%d", &u); f2+=dep[u]; } if(f1<=f2) printf("Bob\n"); else printf("Alice\n"); } }
#include<stdio.h> #include<string.h> #include<queue> #include<iostream> using namespace std; #define MAXN 10 int n, m1, m2; int degree[MAXN]; int list[MAXN][MAXN]; int dep[MAXN]; void BFS(){ queue<int> q; q.push(0); memset(dep, 0, sizeof(dep)); while(!q.empty()){ int u = q.front(); q.pop(); for(int i=0; i<degree[u]; i++){ int v = list[u][i]; if(dep[v]!=0) continue; q.push(v); dep[v] = dep[u]+1; } } } int main(){ while(scanf("%d%d%d", &n, &m1, &m2)==3){ memset(degree, 0, sizeof(degree)); for(int i=1, x, y; i<n; i++){ scanf("%d%d", &x, &y); list[x][degree[x]++] = y; list[y][degree[y]++] = x; } BFS(); int f1, f2, u; f1 = f2 = 0; for(int i=0; i<m1; i++){ scanf("%d", &u); f1+=dep[u]; } for(int i=0; i<m2; i++){ scanf("%d", &u); f2+=dep[u]; } if(f1<=f2) printf("Bob\n"); else printf("Alice\n"); } }
posted on 2012-05-04 15:45 More study needed. 閱讀(320) 評論(0) 收藏 舉報
浙公網安備 33010602011771號