BZOJ4873[Shoi2017]寿司餐厅——最大权闭合子图

BZOJ4873[Shoi2017]寿司餐厅——最大权闭合子图

大家好,又见面了,我是你们的朋友全栈君。

题目描述

Kiana最近喜欢到一家非常美味的寿司餐厅用餐。每天晚上,这家餐厅都会按顺序提供n种寿司,第i种寿司有一个
代号ai和美味度di,i,不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的,Kiana也可以无限次
取寿司来吃,但每种寿司每次只能取一份,且每次取走的寿司必须是按餐厅提供寿司的顺序连续的一段,即Kiana
可以一次取走第1,2种寿司各一份,也可以一次取走第2,3种寿司各一份,但不可以一次取走第1,3种寿司。由于餐
厅提供的寿司种类繁多,而不同种类的寿司之间相互会有影响:三文鱼寿司和鱿鱼寿司一起吃或许会很棒,但和水
果寿司一起吃就可能会肚子痛。因此,Kiana定义了一个综合美味度di,j(i<j),表示在一次取的寿司中,如果包含
了餐厅提供的从第i份到第j份的所有寿司,吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司需要花费一
些时间,所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次取的寿司时,不止一个综合美味度会被
累加,比如若Kiana一次取走了第1,2,3种寿司各一份,除了d1,3以外,d1,2,d2,3也会被累加进总美味度中。神奇
的是,Kiana的美食评判标准是有记忆性的,无论是单种寿司的美味度,还是多种寿司组合起来的综合美味度,在
计入Kiana的总美味度时都只会被累加一次。比如,若Kiana某一次取走了第1,2种寿司各一份,另一次取走了第2,3
种寿司各一份,那么这两次取寿司的总美味度为d1,1+d2,2+d3,3+d1,2+d2,3,其中d2,2只会计算一次。奇怪的是,
这家寿司餐厅的收费标准很不同寻常。具体来说,如果Kiana一共吃过了c(c>0)种代号为x的寿司,则她需要为这些
寿司付出mx^2+cx元钱,其中m是餐厅给出的一个常数。现在Kiana想知道,在这家餐厅吃寿司,自己能获得的总美
味度(包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度)减去花费的总钱数的最大值是多少。由于她
不会算,所以希望由你告诉她

输入

第一行包含两个正整数n,m,分别表示这家餐厅提供的寿司总数和计算寿司价格中使用的常数。
第二行包含n个正整数,其中第k个数ak表示第k份寿司的代号。
接下来n行,第i行包含n-i+1个整数,其中第j个数di,i+j-1表示吃掉寿司能
获得的相应的美味度,具体含义见问题描述。
N<=100,Ai<=1000

输出

输出共一行包含一个正整数,表示Kiana能获得的总美味度减去花费的总钱数的最大值。

 

点权有正有负,点权计算不重复,选了某些点就必须选其他点。可以看出是最大权闭合子图,用正点权和减掉最小割就能得出答案。

那么怎么建图?

由题目可看出总共有三种点:代号、区间美味度、寿司。

结合三者的关系连边:

1、对于所有区间,如果美味度为正,从源点连过来,如果美味度为负,连到汇点,美味度转正。

2、对于所有区间(i,j),连向(i+1,j)和(i,j-1),容量为INF,表示要选小区间之后才能选大区间。

3、对于所有区间(i,j),连向i和j,容量为INF,表示选了对应寿司才能选这个区间(因为第二种连边,所以不用把i到j所有寿司都连上)。

4、对于所有寿司,连向它们对应代号,容量为INF;连向汇点,容量为a[i]。

5、对于所有代号,连向汇点,容量为为m*a[i]*a[i]。

连完边直接跑最大流就行了。这是我认为最好的一道最大流的题,难点就在于如何建图,建明白图后这道题就能迎刃而解了。

最后附上代码。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int next[100001];
int to[100001];
int val[100001];
int head[100001];
int tot=1;
int q[100001];
int n,m;
int S,T;
int s[120][120];
int vis[1010];
int w[1010];
int a[120];
int id[120][120];
long long ans;
long long sum;
int cnt;
int d[100001];
const int INF=0x3f3f3f3f;
void add(int x,int y,int v)
{
    tot++;
    next[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    val[tot]=v;
    tot++;
    next[tot]=head[y];
    head[y]=tot;
    to[tot]=x;
    val[tot]=0;
} 
bool bfs(int S,int T)
{
    int r=0;
    int l=0;
    memset(d,-1,sizeof(d));
    q[r++]=S;
    d[S]=0;
    while(l<r)
    {
        int now=q[l];
        for(int i=head[now];i;i=next[i])
        {
            if(d[to[i]]==-1&&val[i]!=0)
            {
                d[to[i]]=d[now]+1;
                q[r++]=to[i];
            }
        }
        l++;
    }
    if(d[T]==-1)
    {
        return false;
    }
    else
    {
        return true;
    }
}
int dfs(int x,int flow)
{
    if(x==T)
    {
        return flow;
    }
    int now_flow;
    int used=0;
    for(int i=head[x];i;i=next[i])
    {
        if(d[to[i]]==d[x]+1&&val[i]!=0)
        {
            now_flow=dfs(to[i],min(flow-used,val[i]));
            val[i]-=now_flow;
            val[i^1]+=now_flow;
            used+=now_flow;
            if(now_flow==flow)
            {
                return flow;
            }
        }
    }
    if(used==0)
    {
        d[x]=-1;
    }
    return used;
}
void dinic()
{
    while(bfs(S,T)==true)
    {
        ans+=dfs(S,INF);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            scanf("%d",&s[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            id[i][j]=++cnt;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[a[i]])
        {
            vis[a[i]]=1;
            w[a[i]]=++cnt;
        }
    }
    S=0;
    T=cnt+n+1;
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;i++)
    {
        if(!vis[a[i]])
        {
            vis[a[i]]=1;
            add(w[a[i]],T,m*a[i]*a[i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        add(cnt+i,T,a[i]);
        add(cnt+i,w[a[i]],INF);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(s[i][j]>0)
            {
                sum+=s[i][j];
                add(S,id[i][j],s[i][j]);
                add(id[i][j],cnt+i,INF);
                add(id[i][j],cnt+j,INF);
            }
            else if(s[i][j]<0)
            {
                add(id[i][j],T,-s[i][j]);
                add(id[i][j],cnt+i,INF);
                add(id[i][j],cnt+j,INF);
            }
            if(i!=j)
            {
                add(id[i][j],id[i+1][j],INF);
                add(id[i][j],id[i][j-1],INF);
            }
        }
    }
    dinic();
    sum-=ans;
    printf("%lld",sum);
    return 0;
}

转载于:https://www.cnblogs.com/Khada-Jhin/p/9113363.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107492.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 黑苹果从入门到精通:最详细的VMware安装macOS教程[通俗易懂]

    黑苹果从入门到精通:最详细的VMware安装macOS教程[通俗易懂]前言不知为何,以前我发的两篇关于黑苹果的文章或没过审或被删除,最近SMZDM上有不少优质的黑苹果文章发出来,貌似禁令已开,前段时间在一篇写的很不错的黑果文章下吹牛说今年要写一个系列,故有了这篇文章作为系列的开头。系列的名字起的有点俗,叫做xxx从入门到精通,但是我很喜欢,相信过半的黑果群众都是程序员,作为教程来说这个名字俗但是好用,我也希望这个系列能像其它入门到精通系列一样,让大家学到东西…

  • jq正则表达式_JAVA 正则表达式

    jq正则表达式_JAVA 正则表达式一、JavaScript正则表达式正则表达式(英语:RegularExpression,在代码中常简写为regex、regexp或RE)使用单个字符串来描述、匹配一系列符合某个句法规则的字符串搜索模式。搜索模式可用于文本搜索和文本替换。什么是正则表达式?正则表达式是由一个字符序列形成的搜索模式。当你在文本中搜索数据时,你可以用搜索模式来描述你要查询的内容。正则表达式可以是一个简单的字符,或一个更…

  • python matplotlib 画图保存图片简单例子[通俗易懂]

    python matplotlib 画图保存图片简单例子[通俗易懂]保存的时候遇到过保存空白图像的问题,是因为将plt.savefig(‘./test2.jpg’)放到了plt.show()之后,只要先保存在显示就可以正常保存了。importnumpyasnpimportmatplotlib.pyplotaspltt=np.arange(0,69,1)plt.plot(t,t,’r’,t,t**2,’b’)label=…

  • docker command not found_阿里云socket连接数

    docker command not found_阿里云socket连接数背景介绍阿里云提醒,服务器需由经典网络迁移至专有网络,迁移完成,启动服务时,原本已经运行了几个月的脚本,报错 10049。127.0.0.1测试无误,ping公网IP也没毛病,百思不得姐。解决方法各方查证,结论如下:阿里云有两种网络①经典网络②专有网络经典网络可以直接绑定公网IP,专有网络绑定公网IP??不好意思,不行!!why???客服是这么讲的“这不是经典网…

  • A星算法说明「建议收藏」

    A星算法说明「建议收藏」A*算法说明文章目录前言原理说明如何构造h(n)h(n)h(n)一、欧氏距离二、曼哈顿距离三、其他关于g(n)g(n)g(n)路况设置如何实现完整的流程核心代码a_star.ha_star.cppmap_matrix.hmap_matrix.cpp代码使用示例GUI程序下载链接GUI程序使用说明前言  因为最近要写一个毕业设计,有用到自动寻路的功能,因为我要在一个机器里跑算法然后控制机器人自动按照路线到达目的地,所以用Python等解释型语言或Unity等游戏引擎写这个算法都不太合适,我使用的机器要尽

  • c语言生成随机数数组

    c语言实现获得从0~num-1的随机数组(数组元素不重复,内容是0~num-1),实现的原理是数组乱序,效率高!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号