YAIMH1993的笔记
如果奇迹木有出现,就去创造一个
posts - 29,comments - 0,trackbacks - 0
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 6060;
vector<int> G[maxn];
//int val[maxn];
int n;
int dp[maxn][2];
bool vis[maxn];
void dfs(int u) {
    vis[u] = 1;
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v=G[u][i];
        if(vis[v]) continue;
        dfs(v);
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][1],dp[v][0]);   
    }   
}
int d[maxn];
int main() {
    while(~scanf("%d",&n)) {
        if(n == 0) break;
        for(int i=1;i<=n;i++) {
            scanf("%d",&dp[i][1]);
            dp[i][0] = 0;   
            G[i].clear();
            vis[i] = d[i] = 0;
        }  
        int u,v;
        for(;scanf("%d%d",&u,&v);) {
            if(u + v == 0) break;
            G[v].push_back(u); 
            d[u] = 1; 
        }
        int ans = 0;
        for(int i=1;i<=n;i++) {
            if(!d[i]) {
                dfs(i);
                ans += max(dp[i][0],dp[i][1]);
            }   
        }
        printf("%d\n",ans);
    }
    return 0;   
}
posted on 2012-10-09 02:29 YouAreInMyHeart 阅读(87) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理