HDU 1054 树型dp

#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <climits> #include <cstring> #include <cmath> #include <map> #include <set> #define INF 100000000 using namespace std; int n; vector<int> ma[1515]; int dp[1510]; int fun(int x){ //cout << x << ' ' << vis[x] << endl; if(dp[x]) return dp[x]; int len = ma[x].size(); int tm1 = 1; for(int i =0 ;i < len;i++){ int q = ma[x][i]; if(ma[q].size()){ tm1 += fun(q); } } //cout << tm1 << endl; int tm2 = len; //自己不放 for(int i = 0;i < len;i++){ int q = ma[x][i]; int lenq = ma[q].size(); for(int j = 0;j < lenq;j++){ int p = ma[q][j]; if(ma[p].size()){ tm2 += fun(p); } } } //cout <<tm1 << " aa " << tm2 << endl; return dp[x] = min(tm1,tm2); } int main(){ //freopen("1.txt","r",stdin); while(cin >> n){ for(int i = 0;i < n;i++){ ma[i].clear(); } int v,a,m,s; for(int i = 0;i < n;i++){ scanf("%d:(%d)",&v,&m); if(i == 0){ s = v; } for(int j = 0;j < m;j++){ scanf("%d",&a); ma[v].push_back(a); //建树 } } memset(dp,0,sizeof(dp)); fun(s); printf("%d ",dp[s]); } return 0; }