POJ 1909 Marbles on a tree G++ dfs 没掌握

xiaoxiao2021-02-28  128

#include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; //英语 看博友分析 抄博友程序 dfs 没掌握 vector<int> g[10010]; int num[10010]; int rd[10010]; int ans; void dfs(int x)//没掌握 { for(int i=0;i<g[x].size();i++) { int t=g[x][i]; dfs(t); num[x]+=num[t]; ans+=abs(num[t]); } num[x]=num[x]-1; } int main() { while(1) { int n; cin>>n; if(n==0) { break; } for(int i=0;i<10010;i++) { g[i].clear(); } memset(num,0,sizeof(num)); memset(rd,0,sizeof(rd)); ans=0; for(int i=1;i<=n;i++) { int a,b,c; cin>>a>>b>>c; num[a]=b; for(int j=1;j<=c;j++) { int t; cin>>t; g[a].push_back(t); rd[t]++; } } for(int i=1;i<=n;i++) { if(rd[i]==0)//根节点 { dfs(i); break; } } cout<<ans<<endl; } return 0; }

 

转载请注明原文地址: https://www.6miu.com/read-35141.html

最新回复(0)