首页 > 代码库 > HDU3452_Bonsai

HDU3452_Bonsai

2024-07-10 22:04:55   215人阅读

题目的意思是给你一个棵树，每天边上有一个权值，现在要想根节点和每个叶子节点完全隔离开来，删除一些边，求最少需要删除的边权值综合是多少？

直接建模，以根节点为汇点，每个叶子节点连接虚拟源点流量无穷，树上的节点按原样建模就可以了。

最后跑一遍最大流等于最小割，完美解决。

 

召唤代码君：

 

 

#include <iostream>#include <cstdio>#include <cstring>#define maxn 20010#define inf 1999999999using namespace std;int first[maxn],to[maxn],c[maxn],next[maxn],N;int d[maxn],a[maxn],can[maxn],tag[maxn],TAG=520;int s,t,n,m,ans;int Q[maxn],bot,top;void _init(){    N=-1,ans=0,s=0,t=m;    for (int i=0; i<=n; i++) first[i]=-1,a[i]=0;}void edge(int U,int V,int W){    N++;    to[N]=V,c[N]=W,next[N]=first[U],first[U]=N;}void _input(){    int U,V,W;    for (int i=1; i<n; i++)    {        scanf("%d%d%d",&U,&V,&W);        edge(U,V,W),edge(V,U,W);        a[U]++,a[V]++;    }    for (int i=1; i<=n; i++)        if (a[i]==1 && i!=t) edge(s,i,inf),edge(i,s,0);}bool bfs(){    TAG++;    Q[bot=top=1]=t,d[t]=1,tag[t]=TAG;    while (bot<=top)    {        int cur=Q[bot++];        for (int i=first[cur]; i!=-1; i=next[i])        {            if (c[i^1]<=0 || tag[to[i]]==TAG) continue;            d[to[i]]=d[cur]+1,Q[++top]=to[i],tag[to[i]]=TAG;            //if (to[i]==s) return true;        }    }    return tag[s]==TAG;    return false;}int dfs(int cur,int num){    if (cur==t) return num;    int tmp=num,k;    for (int i=first[cur]; i!=-1; i=next[i])    {        if (c[i]<=0 || tag[to[i]]!=TAG || d[to[i]]!=d[cur]-1 || can[to[i]]==TAG) continue;        k=dfs(to[i],min(num,c[i]));        if (k) c[i]-=k,c[i^1]+=k,num-=k;        if (num==0) break;    }    if (num) can[cur]=TAG;    return tmp-num;}int main(){    while (scanf("%d%d",&n,&m)&&(n|m))    {        _init();        _input();        while (bfs()) ans+=dfs(s,inf);        printf("%d\n",ans);    }    return 0;}

　　


联系
我们