【BZOJ3876】支线剧情（AHOI&JSOI2014）-有上下界费用流

做法：本题需要用到有上下界费用流。
我们发现题目要求的就是，以点

)内，这就是有上下界的可行流了。
我们先讨论无源汇的可行流（循环流）要怎么做，由于每条边的下界的存在，那么这条边的两个端点就有必要的出流量和必要的入流量，我们可以建一个超级源点

)边上即可。
可是这道题是有源汇的，这要怎么办呢？其实很简单，只要从所有汇点向源点连一条容量为正无穷的边即可，这样就可以转化为无源汇的问题，那么应用上面的方法做即可。
这道题卡时间啊……要卡进总时间的话，对于一个点

0所以对答案没有影响，这样就可以卡进总时间了，但分点测试无论如何也过不去，有待学习更加好的优化方法。
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1000000000ll*1000000000ll;
int n,S,T,first[310]={0},tot=1;
int laste[310],last[310];
ll dis[310];
bool vis[310];
queue<int> Q;
struct edge
{
    int v,next;
    ll f,c;
}e[100010];

void insert(int a,int b,ll f,ll c)
{
    e[++tot].v=b,e[tot].next=first[a],e[tot].f=f,e[tot].c=c,first[a]=tot;
    e[++tot].v=a,e[tot].next=first[b],e[tot].f=0,e[tot].c=-c,first[b]=tot;
}

void init()
{
    scanf("%d",&n);
    S=n+1,T=n+2;
    for(int i=1;i<=n;i++)
    {
        int k,x;
        ll t,f=0;
        scanf("%d",&k);
        while(k--)
        {
            scanf("%d%lld",&x,&t);
            insert(S,x,1,t);
            insert(i,x,inf,t);
            f++;
        }
        insert(i,T,f,0);
        if (i>1) insert(i,1,inf,0);
    }
}

bool spfa()
{
    for(int i=1;i<=T;i++)
        dis[i]=inf;
    dis[S]=0;
    vis[S]=1;
    Q.push(S);
    while(!Q.empty())
    {
        int v=Q.front();Q.pop();
        for(int i=first[v];i;i=e[i].next)
            if (e[i].f&&dis[e[i].v]>dis[v]+e[i].c)
            {
                dis[e[i].v]=dis[v]+e[i].c;
                laste[e[i].v]=i;
                last[e[i].v]=v;
                if (!vis[e[i].v]) Q.push(e[i].v),vis[e[i].v]=1;
            }
        vis[v]=0;
    }
    return dis[T]!=inf;
}

void mincost()
{
    ll minc=0;
    while(spfa())
    {
        int x=T;
        ll maxf=inf;
        while(x!=S)
        {
            maxf=min(maxf,e[laste[x]].f);
            x=last[x];
        }
        x=T;
        while(x!=S)
        {
            e[laste[x]].f-=maxf;
            e[laste[x]^1].f+=maxf;
            x=last[x];
        }
        minc+=maxf*dis[T];
    }
    printf("%lld",minc);
}

int main()
{
    init();
    mincost();

    return 0;
}

【BZOJ3876】支线剧情（AHOI&JSOI2014）-有上下界费用流

相关推荐