题解 P4189 [CTSC2010]星际旅行

编程 洛谷 题解 CTSC2010

首先先亮出原题

Description
公元3000年，地球联盟已经攻占了银河系内的N个星球，出于资金的考虑，政府仅仅在星球间建立了N-1条双向时空隧道保证任意两个星球之间互相可达。出于管理上的考虑，第i个星球的行政长官要求每个公民在一年内不得从该星球利用时空隧道次数超过Hi次（这一统计是基于离开次数统计的，如果你已经使用从该星球离开过Hi次，那么这一年内你就不能再使用时空隧道离开这个星球了）。Louis
Paosen是一个星际旅行家，他希望能使用尽量多次的时空隧道，但又不希望最终被迫定居的星球条件太过恶劣。所以他希望能知道对于每个星球i，若从0号星球出发，最终以i号星球为终点，这样的星际旅行途中最多可以使用多少次时空隧道。
Input
第一行包含一个整数N。接下来的一行包含N个整数Hi，分别表示每个星球的离开次数限制。接下来N-1行每行两个整数，表示这两个星球之间有时空隧道连接。星球的编号从0开始，Louis
Paosen一开始在0号星球。 Output 包含N行，每行一个整数，表示如果最终旅行结束在这个星球，最多可以使用时空隧道的次数。

题解部分

发现首先可以全走一遍回到起点，然后贪心地消掉还能走的边，这样就得到了回到原点的最大步数。
接下来考虑再走到每个点。dfs一遍，如果父节点还有剩余流量就直接走过来，否则需要退掉向父节点走的边，然后再检查一下多出来的流量能否和儿子走来回。注意需要回溯。

参考代码（$注：有防抄袭$）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
int rd()
{
    int x=0;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0'
        c=getchar();
    }
    return x;
}
int fir[50010],ne[100010],to[100010],w[50010],du[50010],n;
LL now,ans[50010];
void add(int num,int u,int v)
{
    ne[num]=fir[u];
    fir[u]=num;
    to[num]=v;
}
void dfs1(int u,int fa)
{
    LL x;
    int v;
    for (int i=fir[u];i;i=ne[i])
        if ((v=to[i])!=fa)
        {
            dfs1(v,u);
            x=min(w[u],w[v]);
            w[u]-=x;
            w[v]-=x;
            now+=2*x;
        }
}
void dfs2(int u,int fa)
{
    int v,flag;
    if (fa!=-1&&w[fa])
    {
        flag=1;
        w[fa]--;
        now++;
    }
    else
    {
        flag=0;
        now--;
        w[u]++;
        if (w[u]==1)
            for (int i=fir[u];i;i=ne[i])
                if ((v=to[i])!=fa&&w[v])
                {
                    w[u]--;
                    w[v]--;
                    now+=2;
                    flag=-1;
                    break;
                }
    }
    ans[u]=now;
    for (int i=fir[u];i;i=ne[i])
        if ((v=to[i])!=fa)
            dfs2(v,u);
    if (flag==1)
    {
        w[fa]++;
        now--;
    }
    else
    {
        now++;
        if (flag==-1) now-=2;
    }
}
int main()
{
    int u,v;
    n=rd();
    for (int i=1;i<=n;i++) w[i]=rd();
    for (int i=1;i<n;i++)
    {
        u=rd()+1;
        v=rd()+1;
        du[u]++;
        du[v]++;
        add(i<<1,u,v)
        add(i<<1|1,v,u)
    }
    for (int i=1;i<=n;i++) w[i]-=du[i];
    now=2*(n-1);
    dfs1(1,-1);
    ans[1]=now;
    for (int i=fir[1];i;i=ne[i]) dfs2(to[i],1);
    for (int i=1;i<=n;i++) printf("%lld\n",ans[i]);
}  

完结撒花（逃