BZOJ3876:[Ahoi2014]支线剧情 有上下界网络流

思路:

首先建立有上下界的网络流模型:

\[S->1~cap=[0,INF]~cost=0\]

\[i->T~cap=[0,INF]~cost=0(1\leq{i}\leq{n})\]

\[x->y~cap=[1,INF]~cost=w_{x->y}(ForEach x->y)\]

显然是有源汇的上下界网络流模型,我们对下界不为0的边拆边变成只有上界的网络流模型:

设立附加源\(SS\),附加汇\(\ST),则对于:

\[a->b~cap=[l,r]~cost=w_{a->b}\]

我们这样转化:

(1)\[SS->b~Maxcap=l~cost=w_{a->b}\]

(2)\[a->ST~Maxcap=l~cost=0\]

(3)\[a->b~Maxcap=r-l~cost=w_{a->b}\]

注意:(1)(2)中只有一种边的费用为原来费用,另一种边的费用为0.(至于为什么这样连先挖坑)

我们还需要连:

\[T->S~Maxcap=INF~cost=0\]

然后就可以用最小费用最大流水过了.(有时间试试单纯形)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x3f3f3f3f
 
int cnt;
queue<int>q;
struct Solver{
    int head[5100],next[50010],end[50010],flow[50010],cost[50010],ind;
    int d[5100],used[5100],slack[5100],id;bool inq[5100];
    inline void reset(){ind=0,id=1,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q++]=c;}
    inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);}
    inline void spfa(int S,int T){
        memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S);
        while(!q.empty()){
            int i=q.front();q.pop(),inq[i]=0;
            for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                d[end[j]]=d[i]+cost[j];
                if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }for(int i=0;i<=cnt;++i)d[i]=d[T]-d[i];
    }
    inline bool Newlabel(){
        int Min=INF;for(int i=0;i<=cnt;++i)if(used[i]!=id&&slack[i]<Min)Min=slack[i];
        if(Min==INF)return 0;
        for(int i=0;i<=cnt;++i)if(used[i]==id)used[i]=-1,d[i]+=Min;return 1;
    }
    int Getflow(int p,int T,int maxflow){
        if(p==T)return maxflow;
        used[p]=id;
        for(int j=head[p];j!=-1;j=next[j]){
            if(flow[j]&&used[end[j]]!=id&&d[end[j]]+cost[j]==d[p]){
                int to=Getflow(end[j],T,maxflow<flow[j]?maxflow:flow[j]);if(to){flow[j]-=to,flow[j^1]+=to;return to;}
            }else if(flow[j])slack[end[j]]=min(slack[end[j]],d[end[j]]+cost[j]-d[p]);
        }return 0;
    }
    int Mincost(int S,int T){
        int res(0),get;spfa(S,T);
        do{
            memset(slack,0x3f,sizeof slack);
            while((get=Getflow(S,T,INF)))res+=d[S]*get,++id;
        }
        while(Newlabel());
        return res;
    }
}SteinsGate;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    int n;scanf("%d",&n);
    cnt=n;int SS=0,ST=++cnt,S=++cnt,T=++cnt;
    SteinsGate.reset();
 
    int t,a,c;register int i,j;
    SteinsGate.make(S,1,INF,0);
    for(i=1;i<=n;++i){
        SteinsGate.make(i,T,INF,0);
        scanf("%d",&t);
        while(t--)scanf("%d%d",&a,&c),SteinsGate.make(SS,a,1,c),SteinsGate.make(i,ST,1,0),SteinsGate.make(i,a,INF,c);
    }
    SteinsGate.make(T,S,INF,0);
 
    printf("%d",SteinsGate.Mincost(SS,ST));
 
    return 0;
}