gsu 2524 Frozen Rose-Heads

不知道是什么算法，特别像网络流。但是我找不到汇点。最后深搜，在运用DINIC寻找最小流的类似思想，唉。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int head[3005],root[3005],f[3005];
struct node
{
    int v,f;
    int nxt;
}edge[3005];

int nume;
void add(int u,int v,int f)
{
    edge[++nume].v=v; edge[nume].f=f;edge[nume].nxt=head[u];head[u]=nume;
    edge[++nume].v=u;edge[nume].f=f;edge[nume].nxt=head[v];head[v]=nume;
}

void dfs(int u)
{
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].v;
        if(v!=root[u]){
            root[v]=u;
            dfs(v);
            if(f[v]) f[u]+=min(f[v],edge[i].f);
            else f[u]+=edge[i].f;
        }
    }
}

int main()
{
    int n,src,i;
    while(scanf("%d%d",&n,&src)!=EOF){
        nume=1;
        memset(head,-1,sizeof(head));
        memset(root,0,sizeof(root));
        memset(f,0,sizeof(f));
        for(i=1;i<n;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
        }
        dfs(src);
        printf("%d\n",f[src]);
    }
}

gsu 2524 Frozen Rose-Heads,布布扣,bubuko.com

gsu 2524 Frozen Rose-Heads

原文：http://blog.csdn.net/cnh294141800/article/details/21041913