【codevs1380】没有上司的舞会

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 using namespace std;
 6 int n,w[6001],ne=0;
 7 bool in[6001];
 8 int f[6001][2];
 9 int hd[6001];
10 inline int r() {
11     int x=0,f=1;
12     char ch=getchar();
13     while(ch>‘9‘||ch<‘0‘) {
14         if(ch==‘-‘) f=-1;
15         ch=getchar();
16     }
17     while(ch>=‘0‘&&ch<=‘9‘) {
18         x=x*10+ch-‘0‘;
19         ch=getchar();
20     }
21     return x*f;
22 }
23 
24 struct data {
25     int v,next;
26 } e[6001];
27 void add(int v,int u) {
28     ne++;
29     e[ne].v=v;
30     e[ne].next=hd[u];
31     hd[u]=ne;
32 }
33 void dp(int u) {
34     f[u][1]=w[u];
35     f[u][0]=0;
36     for(int p=hd[u]; p!=0; p=e[p].next) {
37         int v=e[p].v;
38         dp(v);
39         f[u][1]+=f[v][0];
40         f[u][0]=f[u][0]+max(f[v][1],f[v][0]);
41     }
42 }
43 int main() {
44     n=read();
45     int l,k;
46     for(int i=1; i<=n; i++)
47         w[i]=read();
48     while(l=read(),k=read()) {
49         if(l==0&&k==0)break;
50         in[l]=1;
51         add(l,k);
52     }
53     for(int i=1; i<=n; i++)
54         if(!in[i]) {
55             dp(i);
56             cout<<max(f[i][0],f[i][1])<<endl;
57             break;
58         }
59     return 0;
60 }