题目地址：http://poj.org/problem?id=1463
题目：
| Time Limit: 2000MS | Memory Limit: 10000K | |
| Total Submissions: 7929 | Accepted: 3692 |
Description
Input
Output
Sample Input
4 0:(1) 1 1:(2) 2 3 2:(0) 3:(0) 5 3:(3) 1 4 2 1:(1) 0 2:(0) 0:(0) 4:(0)
Sample Output
1 2
Source
#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> #define PB push_back #define MP make_pair using namespace std; typedef long long LL; #define PI acos((double)-1) #define E exp(double(1)) const int K=1500+2; short vis[K],head[K],cnt; struct Edge { short next,to; }edge[K*2]; void add(int u,int v) { edge[cnt].next=head[u]; edge[cnt].to=v; head[u]=cnt++; } void dfs(int x,int &v1,int &v2) { v1=1;v2=0; vis[x]=1; int x1,x2; for(int i=head[x];~i;i=edge[i].next) { int v=edge[i].to; if(vis[v])continue; dfs(v,x1,x2); v1+=min(x1,x2); v2+=x1; } } int main(void) { int n; while(~scanf("%d",&n)) { cnt=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { int u,v,k; scanf("%d:(%d)",&u,&k); while(k--) scanf("%d",&v),add(u,v),add(v,u); } int x,y; dfs(0,x,y); printf("%d\n",min(x,y)); } return 0; }
原文：http://www.cnblogs.com/weeping/p/5826797.html