Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

900题留念

Posted by Liuzhaoliang at 2014-10-21 12:11:37 on Problem 1935
#include<iostream>
#include<stdio.h>
#include<vector>
#include<limits.h>
#include<string.h>
using namespace std;
const int N = 50010;
struct E{
    int v,w,next;
}elist[N<<1];
int head[N];
int e_cnt;
int n,k;
int city[N];
int dp[N][2]; // 0 not coming back, 1 coming back
void addedge(int a,int b,int c){
    elist[e_cnt].v = b;
    elist[e_cnt].w = c;
    elist[e_cnt].next = head[a];
    head[a] = e_cnt++;
}
void dfs(int u,int f){
    dp[u][0] = dp[u][1] = 0;
    int m = 0;
    for(int i=head[u];i!=-1;i=elist[i].next){
        int v = elist[i].v;
        int w = elist[i].w;
        if(v==f)continue;
        dfs(v,u);
        if(!dp[v][1] && !city[v]) continue;
        dp[u][0] += 2*w+dp[v][1];
        dp[u][1] += 2*w+dp[v][1];
        m = max(m,w+dp[v][1]-dp[v][0]);
    }
    dp[u][0] -= m;
}
int main()
{
    int a,b,c;
    scanf("%d%d",&n,&k);
    e_cnt = 0;
    memset(head,-1,sizeof head);
    for(int i=0;i<n-1;i++){
        scanf("%d%d%d",&a,&b,&c);
        addedge(a,b,c);
        addedge(b,a,c);
    }
    int cnt,x;
    scanf("%d",&cnt);
    while(cnt--){
        scanf("%d",&x);
        city[x] =1;
    }
    dfs(k,0);
    printf("%d\n",min(dp[k][0],dp[k][1]));
    
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator