题意：给你一棵数，每个桥有两种状态，好或者坏，要求你求最小的节点集合，使得修复所有的坏桥（选一个点以后，这个点到1节点之间所有的桥都变好）
解题思路：两次dfs 第一次判断这个支路或者后续有没有坏桥，第二个dfs求点集合
解题代码
1 // File Name: c.c 2 // Author: darkdream 3 // Created Time: 2014年11月30日 星期六 00时09分50秒 4 5 #include<stdio.h> 6 #include<string.h> 7 #include<stdlib.h> 8 #include<time.h> 9 #include<math.h> 10 #pragma comment(linker,"/STACK:102400000,102400000") 11 #define maxn 200005 12 struct node{ 13 int v; 14 int is; 15 struct node *next; 16 }map[maxn]; 17 int num[maxn]; 18 struct node *newnode(int a,int c) 19 { 20 struct node *p = (node*)malloc(sizeof(node)); 21 p->v = a ; 22 if(c == 1) 23 p->is = 1; 24 else p->is = 0; 25 p->next = NULL; 26 return p; 27 } 28 int ansnum = 0 ; 29 int ans[maxn]; 30 int ok[maxn]; 31 int visit[maxn]; 32 int dfs(int k ) 33 { 34 struct node *p = &map[k]; 35 int t = 0 ; 36 for(int i =1 ;i <= num[k]; i ++) 37 { 38 p = p->next; 39 if(!visit[p->v]) 40 { 41 visit[p->v] = 1; 42 if(!p->is) 43 {ok[k] = 1; 44 ok[p->v] = 1; 45 } 46 if(dfs(p->v)) 47 ok[k] = 1; 48 } 49 } 50 if(ok[k]) 51 return 1; 52 else return 0; 53 } 54 55 void dfs1(int k) 56 { 57 struct node *p = &map[k]; 58 int t = 0 ; 59 for(int i =1 ;i <= num[k]; i ++) 60 { 61 p = p->next; 62 if(!visit[p->v] && ok[p->v]) 63 { 64 t ++; 65 visit[p->v] = 1; 66 dfs1(p->v); 67 } 68 } 69 if(t == 0 && ok[k] ) 70 { 71 ansnum ++; 72 ans[ansnum] = k ; 73 return ; 74 } 75 76 } 77 int main(){ 78 int n; 79 scanf("%d",&n); 80 memset(num,0,sizeof(num)); 81 memset(map,0,sizeof(map)); 82 memset(ok,0,sizeof(ok)); 83 for(int i =1;i <= n -1;i ++) 84 { 85 int ta,tb,tc; 86 scanf("%d %d %d",&ta,&tb,&tc); 87 88 num[ta]++; 89 struct node *p = newnode(tb,tc); 90 struct node *temp ; 91 temp = map[ta].next; 92 map[ta].next = p; 93 p->next = temp; 94 95 96 num[tb]++; 97 p = newnode(ta,tc); 98 temp = map[tb].next; 99 map[tb].next = p; 100 p->next = temp; 101 102 } 103 memset(visit,0,sizeof(visit)); 104 visit[1] = 1 ; 105 dfs(1); 106 /* for(int i =1 ;i <=n;i ++) 107 printf("%d ",ok[i]); 108 printf(" ");*/ 109 memset(visit,0,sizeof(visit)); 110 visit[1] = 1; 111 dfs1(1); 112 printf("%d ",ansnum); 113 for(int i= 1 ;i <= ansnum ;i ++) 114 { 115 printf("%d ",ans[i]); 116 } 117 118 return 0 ; 119 }
同时 看到一种更优美的解法
1 #include <vector> 2 #include <map> 3 #include <set> 4 #include <deque> 5 #include <stack> 6 #include <queue> 7 #include <algorithm> 8 #include <functional> 9 #include <numeric> 10 #include <utility> 11 #include <sstream> 12 #include <iostream> 13 #include <iomanip> 14 #include <cstdio> 15 #include <cmath> 16 #include <cstdlib> 17 #include <ctime> 18 #include <cstring> 19 using namespace std; 20 21 #pragma comment(linker,"/STACK:33554432") 22 23 #define eps 1e-9 24 #define pb push_back 25 #define mp make_pair 26 #define fr first 27 #define sc second 28 #define sz(v) ((int)(v).size()) 29 #define all(v) v.begin(),v.end() 30 #define same(a,b) (fabs((a)-(b))<eps) 31 #define set(arr,with) memset(arr,with,sizeof(arr)) 32 #define add(target,value,mod) target = (target+value)%(mod) 33 #define put_min(target,value) target = min(target,value) 34 #define put_max(target,value) target = max(target,value) 35 typedef pair<int,int> pii; 36 typedef long long lld; 37 38 #define MAXN 100005 39 40 int N,D[MAXN]; 41 bool chk[MAXN],V[MAXN]; 42 vector <int> con[MAXN],ans; 43 44 void dfs(int n) 45 { 46 V[n] = 1; 47 int i,k,t; 48 for (i=0;i<sz(con[n]);i+=2){ 49 k = con[n][i], t = con[n][i+1]; 50 if (V[k]) continue; 51 if (t == 2) chk[k] = 1, D[n]++; 52 dfs(k); 53 D[n] += D[k]; 54 } 55 } 56 57 int main() 58 { 59 int i,j,k,t; 60 scanf("%d",&N); 61 for (i=1;i<N;i++){ 62 scanf("%d%d%d",&j,&k,&t); 63 con[j].pb(k), con[j].pb(t); 64 con[k].pb(j), con[k].pb(t); 65 } 66 dfs(1); 67 for (i=2;i<=N;i++) if (chk[i] && !D[i]) ans.pb(i); 68 printf("%d ",sz(ans)); 69 for (i=0;i<sz(ans);i++) printf("%d ",ans[i]); puts(""); 70 }
BY： Myungwoo