Loading...

洛谷P3931 SAC E#1 - 一道难题 Tree

check评论:0 条 remove_red_eye浏览量:483 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-11

其实这题如果按网络流做,难度是不止普及+的qwq

因为我不会树形dp

这道题既然是找最小割,自然就想到了最大流

我们设一个超级汇点,所有叶子结点向其连边,一遍$dfs$就可以判断哪些是叶子

然后从根向超级汇点跑最大流救星

#include <bits/stdc++.h>
using namespace std;
int head[100010],head1[100010],outd[100010],cnt,n,s,fa[100010],t;
int dis[100010],vis[100010];
struct edge
{
    int next,to,dis;
}et[200020],e[800020];
void addt(int u,int v,int dis)
{
    cnt++;
    et[cnt].to=v;
    et[cnt].next=head1[u];
    et[cnt].dis=dis;
    head1[u]=cnt;
} 
void add(int u,int v,int dis)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
} 
void tdfs(int u)
{
    for(int i=head1[u];i;i=et[i].next)
    {
        int v=et[i].to;
        if(v==fa[u])
        {
            continue;
        }
        fa[v]=u;
        outd[u]=1;
        tdfs(v);
    }
}
int bfs()
{
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    vis[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]==-1&&e[i].dis>0)
            {
                dis[v]=dis[u]+1;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v); 
                }
            }
        }
    }
    return dis[t]!=-1;
}
int dfs(int u,int exp)
{
    if(u==t||!exp)
    {
        return exp;
    }
    int flow=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(dis[v]==dis[u]+1&&e[i].dis>0)
        {
            int tmp=dfs(v,min(exp,e[i].dis));
            if(!tmp)
            {
                continue;
            }
            exp-=tmp;
            flow+=tmp;
            e[i].dis-=tmp;
            e[i^1].dis+=tmp;
            if(!exp)
            {
                break;
            }
        }
    }
    return flow;
}
int main()
{
    cin>>n>>s;
    t=n+1;
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        addt(x,y,z);
        addt(y,x,z);
    }
    tdfs(s);
    cnt=1;
    for(int i=1;i<=n;i++)
    {
        if(!outd[i])
        {
            add(i,t,0x3f3f3f3f);
            add(t,i,0);
            continue;
        }
        for(int j=head1[i];j;j=et[j].next)
        {
            int v=et[j].to;
            if(v==fa[i])
            {
                continue;
            }
            add(i,v,et[j].dis);
            add(v,i,0);
        }
    }
    int ans=0;
    while(bfs())
    {
        ans+=dfs(s,0x3f3f3f3f);
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名