标签：open tac pre one amp com 图片 拓扑排序 out
1.家谱树
寻寻有一个大家庭，辈分关系很混乱，请你帮他梳理一下家庭成员的关系。
输入：
第一行n，表示共5个人。
接下来的n行，第i行表示第i个人的孩子。
每行以0结束。
输出：
一行序列，空格隔开，使得每个人的后辈都比那个人后出现。
spj
#include
#include
#include
#include
#include
#include
#include
#includeusing namespace std;
int n,cnt,ru[10005],hd[10005],ans, x,t,y;
stackint> q;
struct Edge{
int to, nxt;
}edge[1000005];
void add(int u, int v){
cnt++;
edge[cnt].to = v;
edge[cnt].nxt = hd[u];
hd[u] = cnt;
}
int main(){
scanf("%d",&n);
for(int i = 1; i ){
while(~scanf("%d",&y)){
if(y == 0) break;
add(i,y);
ru[y]++;
}
}
int mx = 0;
for(int i = 1; i )
if(ru[i] == 0){
q.push(i);
}
while(!q.empty()){
int u = q.top(); q.pop();
printf("%d ",u);
for(int i = hd[u]; i; i = edge[i].nxt){
int v = edge[i].to;
ru[v]--;
if(!ru[v]){
q.push(v);
}
}
}
return 0;
}
/*
5
0
4 5 0
1 0
5 3 0
3 0
*/
View Code
P1113 杂务
题解：递推关系
#include
#include
#include
#include
#include
#include
#include
#includeusing namespace std;
int n,cnt,at[10005],ru[10005],hd[10005],ans, x,t,y, f[10005];
stackint> q;
struct Edge{
int to, nxt;
}edge[1000005];
void add(int u, int v){
cnt++;
edge[cnt].to = v;
edge[cnt].nxt = hd[u];
hd[u] = cnt;
}
int main(){
scanf("%d",&n);
for(int i = 1; i ){
scanf("%d%d",&x,&t);
at[x] = t;
while(~scanf("%d",&y)){
if(y == 0) break;
add(y,x);
ru[x]++;
}
}
int mx = 0;
for(int i = 1; i )
if(ru[i] == 0){
q.push(i);
f[i] = at[i];
}
while(!q.empty()){
int u = q.top(); q.pop();
for(int i = hd[u]; i; i = edge[i].nxt){
int v = edge[i].to;
ru[v]--;
if(!ru[v]){
q.push(v);
}
f[v] = max(f[v], f[u] + at[v]);
}
}
for(int i = 1; i )
ans = max(ans, f[i]);
printf("%d\n",ans);
return 0;
}
// #include// #include// #include// #include// #include
// #include// #include// #include// using namespace std;
// int n,cnt,at[10005],ru[10005],hd[10005],ans, x,t,y, vis[10005];
// stack q;
// struct Edge{
// int to, nxt;
// }edge[1000005];
// void add(int u, int v){
// cnt++;
// edge[cnt].to = v;
// edge[cnt].nxt = hd[u];
// hd[u] = cnt;
// }
// int main(){
// scanf("%d",&n);
// for(int i = 1; i // scanf("%d%d",&x,&t);
// at[x] = t;
// while(~scanf("%d",&y)){
// if(y == 0) break;
// add(y,x);
// ru[x]++;
// }
// }
// int fl;
// while(1){
// int mx = 0, fl = 0;
// cout// for(int u = 1; u // if(!ru[u] && !vis[u]){
// q.push(u);
// if(at[u] > mx) mx = at[u];
// fl = 1;
// vis[u] = 1;
// cout// }
// }
//
// cout// if(!fl) break;
// ans += mx;
// cout// cout// while(!q.empty()){
// int u = q.top(); q.pop();
// for(int i = hd[u]; i; i = edge[i].nxt){
// int v = edge[i].to;
// ru[v]--;
// cout// }
// }
// cout// }
// printf("%d\n",ans);
// return 0;
// }
View Code
拓扑排序
标签：open tac pre one amp com 图片 拓扑排序 out
原文地址：https://www.cnblogs.com/caterpillor/p/13604941.html