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

作者: wjyyy 分类: 上下界网络流,可行流,网络流,解题报告,费用流 发布时间: 2019-01-19 11:49

点击量:64

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

题目背景

宅男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;
}

3
说点什么

avatar
3 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
wjyyy Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 题目链接 题解 […]

wjyyy
游客

……突然发现这个题可以不用存ori,因为是最小费用最大流。但是存了ori应该会更好调试一些。

trackback

[…] 【有源汇无限流】_并不裸_ […]

/* */