Ahoi2014&Jsoi2014 支线剧情

题目描述

题解：

每条边至少经过一次，说明经过下界为$1$。

然后套有源汇上下界最小费用可行流板子。

口胡一下。

此类问题的建图通式为：

1.假设原来的边流量上下界为$[l,r]$，那么在新图中建流量上界为$(r-l)$的边；

就是必须流的先流完，不一定的一会再算。

2.统计一下每个点流入的$l$之和$ind$以及流出的$l$之和$otd$，设$d=ind-otd$；

若$d>0$，则建一条从新源点到该点的、容量为$d$的边，表示减下界的时候多减了，要加回来；

若$d<0$，则建一条从该点到新汇点的、容量为$-d$的边，表示加多了，要减回来。

3.旧汇点->旧源点，容量为$inf$，有借有还再借不难

然后求新图的最小费用最大流，答案即为最小费用+所有边的费用*下界。

代码：

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = ;

const int inf = 0x3f3f3f3f;

const ll  Inf = 0x3f3f3f3f3f3f3f3fll;

template<typename T>

inline void read(T&x)

{

    T f = ,c = ;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}

    x = f*c;

}

int n,hed[N],cnt=-,S,T,otd[N],ind[N],SS,TT;

struct EG

{

    int to,nxt;

    ll f,w;

}e[*N];

void ae(int f,int t,ll fl,ll wl)

{

    e[++cnt].to = t;

    e[cnt].nxt = hed[f];

    e[cnt].f = fl;

    e[cnt].w = wl;

    hed[f] = cnt;

}

void AE(int f,int t,ll fl,ll wl)

{

    ae(f,t,fl,wl);

    ae(t,f,,-wl);

}

int pre[N],fa[N];

ll dis[N],fl[N],ans;

bool vis[N];

bool spfa()

{

    queue<int>q;

    memset(dis,0x3f,sizeof(dis));

    dis[SS]=,fl[SS]=Inf,vis[SS]=;q.push(SS);

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        for(int j=hed[u];~j;j=e[j].nxt)

        {

            int to = e[j].to;

            if(e[j].f&&dis[to]>dis[u]+e[j].w)

            {

                dis[to]=dis[u]+e[j].w;

                fl[to]=min(fl[u],e[j].f);

                fa[to]=u,pre[to]=j;

                if(!vis[to])

                {

                    vis[to]=;

                    q.push(to);

                }

            }

        }

        vis[u]=;

    }

    return dis[TT]!=Inf;

}

ll mcmf()

{

    ll ret = ;

    while(spfa())

    {

        ret+=fl[TT]*dis[TT];

        int u = TT;

        while(u!=SS)

        {

            e[pre[u]].f-=fl[TT];

            e[pre[u]^].f+=fl[TT];

            u=fa[u];

        }

    }

    return ret;

}

int main()

{

    read(n);

    S=,T=n+;

    SS=n+,TT=n+;

    memset(hed,-,sizeof(hed));

    for(int k,t,w,i=;i<=n;i++)

    {

        read(k);

        while(k--)

        {

            read(t),read(w);

            ind[t]++,otd[i]++;

            AE(i,t,inf,w);

            ans+=w;

        }

        if(i!=)AE(i,T,inf,);

    }

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

    {

        int d = ind[i]-otd[i];

        if(d<)AE(i,TT,-d,);

        else AE(SS,i,d,);

    }

    AE(T,S,inf,);

    ans+=mcmf();

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

    return ;

}