POJ 3585 Accumulation Degree 题解

题面

一句话题意：找一个点使得，使得从这个点出发作为源点，发出的流量最大，输出这个最大的流量

这道题是换根法+二次扫描的模板；

首先若确定1为原点，那么可以写出dp方程：当v的度是1时， g[u]+=g[v];否则g[u]+=min(g[v],star[i].w);

但以上仅仅是有原点的做法，那么如果没有原点就只能是N^2了吗？当然不仅可能；

我们从上到下开始dfs，设f[i]表示以i为根所能得到的最大值，那么显然：f[1]=g[1];

然后分两种情况：如果u的度是1，那么f[v]=g[u]+star[i].w;

否则,f[v]=g[v]+min(star[i].w,f[u]-min(g[v],star[i].w));

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n;

struct littlestar{

    int to;

    int nxt;

    int w;

}star[];

int head[],cnt;

void add(int u,int v,int w)

{

    star[++cnt].to=v;

    star[cnt].w=w;

    star[cnt].nxt=head[u];

    head[u]=cnt;

}

int g[],f[];

int du[];

void dp(int u,int fa)

{

    g[u]=;

    for(int i=head[u];i;i=star[i].nxt){

        int v=star[i].to;

        if(v==fa) continue;

        dp(v,u);

        if(du[v]==){

            g[u]+=star[i].w;

        }

        else{

            g[u]+=min(g[v],star[i].w);

        }

    }

}

void dfs(int u,int fa)

{

    for(int i=head[u];i;i=star[i].nxt){

        int v=star[i].to;

        if(v==fa) continue;

        if(du[u]==){

            f[v]=g[v]+star[i].w;

        }

        else{

            f[v]=g[v]+min(f[u]-min(star[i].w,g[v]),star[i].w);

        }

        dfs(v,u);

    }

}

int main()

{

    int t;

    cin>>t;

    while(t--){

        memset(head,,sizeof(head));

        cnt=;

        memset(g,,sizeof(g));

        memset(f,,sizeof(f));

        memset(du,,sizeof(du));

        int n;

        cin>>n;

        for(int i=;i<=n-;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            du[u]++;

            du[v]++;

            add(u,v,w);

            add(v,u,w);

        }

        dp(,);

        f[]=g[];

        dfs(,);

        int ans=;

        for(int i=;i<=n;i++) ans=max(ans,f[i]);

        cout<<ans<<endl;

    }

}