洛谷 P4043 [AHOI2014/JSOI2014]支线剧情 题解【网络流】【上下界网络流】【费用流】【可行流】

点击量：272

这个标签是不是有点冗余啊……

目录

题目背景

宅男JYY非常喜欢玩RPG游戏，比如仙剑，轩辕剑等等。不过JYY喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在JYY想花费最少的时间看完所有的支线剧情。

题目描述

JYY现在所玩的RPG游戏中，一共有N个剧情点，由1到N编号，第i个剧情点可以根据JYY的不同的选择，而经过不同的支线剧情，前往Ki种不同的新的剧情点。当然如果为0，则说明i号剧情点是游戏的一个结局了。

JYY观看一个支线剧情需要一定的时间。JYY一开始处在1号剧情点，也就是游戏的开始。显然任何一个剧情点都是从1号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。由于JYY过度使用修改器，导致游戏的“存档”和“读档”功能损坏了，

所以JYY要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到1号剧情点。JYY可以在任何时刻退出游戏并重新开始。不断开始新的游戏重复观看已经看过的剧情是很痛苦，JYY希望花费最少的时间，看完所有不同的支线剧情。

输入输出格式

输入格式：

输入一行包含一个正整数N。

接下来N行，第i行为i号剧情点的信息；

第一个整数为k，接下来k个整数对，Bij和Tij，表示从剧情点i可以前往剧情点Bij，并且观看这段支线剧情需要花费Tij的时间。

输出格式：

输出一行包含一个整数，表示JYY看完所有支线剧情所需要的最少时间。

输入输出样例

输入样例#1：

6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0

输出样例#1：

24

说明

JYY需要重新开始3次游戏，加上一开始的一次游戏，4次游戏的进程是

样例解释

1->2->4，1->2->5，1->3->5和1->3->6。

对于100%的数据满足N<=300,0<=Ki<=50,1<=Tij<=300,Sigma(Ki)<=5000

题解：

最小费用问题。这里需要的是可行流而不是最大流，因为跑满最大流后的费用更多了，而存在一些浪费。

不过由于上下界网络流的附加边这一特性，这个题跑最小费用最大流和最小费用可行流没有什么区别。（也有可能是我建边比较特殊）

一开始把题目理解错了，以为每个点都要经过一次。实际上是要求每条边都经过一次，这是一个DAG，所以边只能正向经过，那么因此（原图上）每条边的下界都是$ 1$。

又由于流量没有限制，所以从每个点向$ 1$号点连接一条容量为$ \inf$，费用为$ 0$的边，就形成了无源汇的上下界网络流问题了。

此时建立上下界，附加边费用为$ 0$，然后跑最小费用最大流。最后加上每条边的边权之和就可以了。

还可以把附加边分开建立，然后把费用加在附加边上，同样是跑最小费用最大流，最后不用加边权。

Code：

#include<cstdio>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
using std::queue;
struct edge
{
    int n,nxt,v,w,ori;
    edge(int n,int nxt,int v,int w,int ori)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
        this->w=w;
        this->ori=ori;
    }
    edge(){}
}e[30000];
//5000对实边、每个点有上下界300
int head[400],ecnt=-1;
//S=0,T=345
void add(int from,int to,int v,int w,int ori)
{
    e[++ecnt]=edge(to,head[from],v,w,ori);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],0,-w,0);
    head[to]=ecnt;
}
int dis[400],pre[400];
bool used[400];
bool spfa()
{
    queue<int> q;
    memset(dis,0x3f,sizeof(dis));
    dis[0]=0;
    used[0]=1;
    q.push(0);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        used[x]=0;
        for(int i=head[x];~i;i=e[i].nxt)
            if(e[i].v&&dis[e[i].n]>dis[x]+e[i].w)
            {
                dis[e[i].n]=dis[x]+e[i].w;
                pre[e[i].n]=i;
                if(!used[e[i].n])
                {
                    used[e[i].n]=1;
                    q.push(e[i].n);
                }
            }
    }
    return dis[345]!=0x3f3f3f3f;
}
int in[400];
int main()
{
    memset(head,-1,sizeof(head));
    int n,k,u,v,sum=0,ans=0;
    pre[0]=-1;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&k);
        add(i,1,inf,0,0);
        add(i,345,k,0,0);
        sum+=k;
        for(int j=1;j<=k;++j)
        {
            scanf("%d%d",&u,&v);
            ans+=v;
            add(i,u,inf,v,inf+1);
            ++in[u];
        }
    }
    for(int i=1;i<=n;++i)
        add(0,i,in[i],0,0);
    while(spfa())
    {
//      puts("1");
        int p=pre[345],mn=inf;
        while(~p)
        {
            mn=mn<e[p].v?mn:e[p].v;
            p=pre[e[p^1].n];
        }
        p=pre[345];
        while(~p)
        {
            e[p].v-=mn;
            e[p^1].v+=mn;
            ans+=e[p].w*mn;
            p=pre[e[p^1].n];
        }
        sum-=mn;
        //if(sum<=0)
        //  break;可以不要
    }
    printf("%d\n",ans);
    return 0;
}