poj3585树最大流——换根法

题目：http://poj.org/problem?id=3585

二次扫描与换根法，一次dfs求出以某个节点为根的相关值，再dfs遍历一遍树，根据之前的值换根取最大值为答案。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,head[],ct,d[],f[],deg[],ans,t;

bool vis[];

struct N{

    int to,next,w;

}edge[];

void add(int x,int y,int z)

{

    ct++;

    edge[ct].to=y;

    edge[ct].next=head[x];

    edge[ct].w=z;

    head[x]=ct;

}

void dp(int x)

{

    vis[x]=;

    for(int i=head[x];i;i=edge[i].next)

    {

        int u=edge[i].to;

        if(vis[u])continue;

        dp(u);

        if(deg[u]==)d[x]+=edge[i].w;

        else d[x]+=min(d[u],edge[i].w);

    }

}

void dfs(int pre,int w,int x)

{

    vis[x]=;

    if(deg[pre]==)f[x]=d[x]+w;

    else f[x]=d[x]+min(f[pre]-min(d[x],w),w);

    ans=max(ans,f[x]);

    for(int i=head[x];i;i=edge[i].next)

    {

        int u=edge[i].to;

        if(vis[u])continue;

        dfs(x,edge[i].w,u);

    }

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        memset(deg,,sizeof deg);

        memset(f,,sizeof f);

        memset(d,,sizeof d);

        memset(head,,sizeof head);

        memset(vis,,sizeof vis);

        ans=;ct=;

        scanf("%d",&n);

        int a,b,c;

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

        {

            scanf("%d%d%d",&a,&b,&c);

            add(a,b,c);

            add(b,a,c);

            deg[a]++;deg[b]++;

        }

        dp();

        f[]=d[];

        memset(vis,,sizeof vis);

        dfs(,,);

        printf("%d\n",ans);

    }

    return ;

}