Problem - 5326
这个题目是个递推,不过由于是树形的,需要dfs来完成递推的过程。
关键在于p[now] += p[to]+1;如果now能manage to的话。
此处采用链式前向星来保存关系图。
http://blog.csdn.net/tc_to_top/article/details/47108595
It's an interesting experience to move from ICPC to work, end my college life and start a brand new journey in company.
As is known to all, every stuff in a company has a title, everyone except the boss has a direct leader, and all the relationship forms a tree. If A's title is higher than B(A is the direct or indirect leader of B), we call it A manages B.
Now, give you the relation of a company, can you calculate how many people manage k people.
As is known to all, every stuff in a company has a title, everyone except the boss has a direct leader, and all the relationship forms a tree. If A's title is higher than B(A is the direct or indirect leader of B), we call it A manages B.
Now, give you the relation of a company, can you calculate how many people manage k people.
Input
There are multiple test cases.
Each test case begins with two integers n and k, n indicates the number of stuff of the company.
Each of the following n-1 lines has two integers A and B, means A is the direct leader of B.
1 <= n <= 100 , 0 <= k < n
1 <= A, B <= n
Each test case begins with two integers n and k, n indicates the number of stuff of the company.
Each of the following n-1 lines has two integers A and B, means A is the direct leader of B.
1 <= n <= 100 , 0 <= k < n
1 <= A, B <= n
Output
For each test case, output the answer as described above.
Sample Input
7 2 1 2 1 3 2 4 2 5 3 6 3 7
Sample Output
2
这个题目是个递推,不过由于是树形的,需要dfs来完成递推的过程。
关键在于p[now] += p[to]+1;如果now能manage to的话。
此处采用链式前向星来保存关系图。
http://blog.csdn.net/tc_to_top/article/details/47108595
- struct EDGE
- {
- int v, next;
- }e[MAX];
- int head[MAX], num[MAX];
- bool in[MAX], vis[MAX];
- int cnt, ans;
- int n, k;
- void Add(int u, int v)
- {
- e[cnt].v = v;
- e[cnt].next = head[u];
- head[u] = cnt ++;
- }
- void DFS(int u)
- {
- vis[u] = true;
- num[u] = 0;
- for(int i = head[u]; i != -1; i = e[i].next)
- {
- int v = e[i].v;
- if(!vis[v])
- {
- DFS(v);
- num[u] += (num[v] + 1);
- }
- }
- if(num[u] == k)
- ans ++;
- return;
- }
- int main()
- {
- while(scanf("%d %d", &n, &k) != EOF)
- {
- cnt = 0;
- ans = 0;
- memset(head, -1, sizeof(head));
- memset(in, false, sizeof(in));
- memset(vis, false, sizeof(vis));
- for(int i = 0; i < n - 1; i++)
- {
- int u, v;
- scanf("%d %d", &u, &v);
- Add(u, v);
- in[v] ++;
- }
- for(int i = 1; i <= n; i++)
- if(in[i] == 0)
- DFS(i);
- printf("%d\n", ans);
- }
- }
http://blog.csdn.net/firenet1/article/details/47129831
http://www.zgxue.com/198/1980697.html
- vector<int>haha[200];
- int check[200];
- int num[200];
- int dfs(int u){
- if(check[u]) return num[u]+1;
- check[u] = 1;
- for(int i = 0; i < haha[u].size();i++)
- num[u] += dfs(haha[u][i]);
- return num[u]+1;
- }
- int main(){
- int n,k;
- while(scanf("%d%d",&n,&k)!=EOF){
- for(int i = 0;i <= n; i++)
- haha[i].clear();
- int u,v;
- for(int i =1;i < n; i++){
- scanf("%d%d",&u,&v);
- haha[u].push_back(v);
- }
- memset(check,0,sizeof(check));
- memset(num,0,sizeof(num));
- int ans = 0;
- for(int i = 1;i <= n; i++){
- if(check[i]) continue;
- dfs(i);
- }
- for(int i =1;i <= n; i++)
- if(num[i]==k) ans++;
- cout<<ans<<endl;
- }
- return 0;
- }
int dfs(int x) 10 { 11 int sum=0; 12 for (int i=1;i<=n;i++) 13 { 14 if (Map[x][i]==1) 15 { 16 sum++; 17 sum+=dfs(i); 18 } 19 } 20 return sum; 21 } 22 23 int main() 24 { 25 int a,b,ans; 26 while (~scanf("%d%d",&n,&m)) 27 { 28 ans=0; 29 memset(Map,0,sizeof(Map)); 30 //memset(ok,0,sizeof(ok)); 31 for (int i=1; i<=n-1; i++) 32 { 33 scanf("%d%d",&a,&b); 34 Map[a][b]=1; 35 } 36 for (int i=1;i<=n;i++) 37 { 38 if (dfs(i)==m) 39 ans++; 40 } 41 printf ("%d\n",ans); 42 } 43 return 0; 44 }X. Reclusive solution - not efficient
http://www.zgxue.com/198/1980697.html
struct node { int num,s[105]; }res[105]; int ans; void judge(int i) { if(res[i].num==0) return ; ans+=res[i].num; for(int j=0;j<res[i].num;j++) judge(res[i].s[j]); } int main() { int n,k,a,b,cnt; while(~scanf("%d%d",&n,&k)) { memset(res,0,sizeof(res)); for(int i=0;i<n-1;i++) { scanf("%d%d",&a,&b); res[a].s[res[a].num]=b; res[a].num++; } cnt=0; for(int i=1;i<=n;i++) { ans=res[i].num; for(int j=0;j<res[i].num;j++) judge(res[i].s[j]); if(ans==k) cnt++; } printf("%d\n",cnt); } return 0; }Read full article from Problem - 5326