• bzoj 4873: [Shoi2017]寿司餐厅


    4873: [Shoi2017]寿司餐厅

    2017-10-05


    Description

    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想知道,在这家餐厅吃寿司,自己能获得的总美
    味度(包括所有吃掉的单种寿司的美味度和所有被累加的综合美味度)减去花费的总钱数的最大值是多少。由于她
    不会算,所以希望由你告诉她

    Input

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

    Output

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

    Sample Input

    3 1
    2 3 2
    5 -10 15
    -10 15
    15

    Sample Output

    12

    当初省选的时候,Day2的T1一看到,额什么东西啊,树+连通块??

    T2一个概率,完全GG,T3好像是一个dp,数据还蛮小的x,就是他了,看了半天题目,Day2爆0了,哈哈哈.

    这个题现在才知道是网络流,(因为关系复杂,所以先花式建边,分几个步骤

    1:如果i=j,令map[i][j]-编号;

    2:map[i][j]>0连源点,并和(i+1,j)(i,j-1)相连;

    3:map[i][j]<0连汇点,并和(i+1,j)(i,j-1)相连;

    建完边跑最小割

    用所有正边权和减去最小割就是答案.

    w同学汇点选1e7,数组竟然只开了8e4,不re才怪哈哈哈哈哈哈哈哈

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int ad=233;
    const int INT=2333333;
    int read(){
        int an=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while('0'<=ch&&ch<='9'){an=an*10+ch-'0';ch=getchar();}
        return an*f;
    }
    bool v[1000+ad];
    int a[100+ad],map[100+ad][100+ad],cnt1,cnt=1;
    int id[100+ad][100+ad],idw[1000+ad];
    int f[20000<<2];
    int n,m,ans,S,T;
    struct saber{
    int nex,to,wi;
    }b[20000<<3];
    inline void add(int x,int y,int z){
        cnt++;
        b[cnt].nex=f[x];
        b[cnt].to=y;
        b[cnt].wi=z;
        f[x]=cnt;
        cnt++;
        b[cnt].nex=f[y];
        b[cnt].to=x;
        b[cnt].wi=0;
        f[y]=cnt;
    }
    int dis[20000<<2];
    queue<int>q;
    bool bfs(){
        while(!q.empty())q.pop();
        memset(dis,-1,sizeof(dis));
        q.push(S);dis[S]=0;
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=f[x];i;i=b[i].nex){
                int v=b[i].to;
                if(dis[v]<0&&b[i].wi){
                    dis[v]=dis[x]+1;
                    q.push(v);
                    if(v==T)return 1;
                }
            }
        }
        if(dis[T]>0)return 1;
        return 0;
    }
    int dfs(int x,int li){
        if(x==T)return li;
        int used=li;
        for(int i=f[x];i;i=b[i].nex){
            int v=b[i].to;
            if(used&&b[i].wi>0&&dis[v]==dis[x]+1){
                int re=dfs(v, min(b[i].wi,used) );
                b[i].wi-=re;
                b[i^1].wi+=re;
                used-=re;
                if(!re)dis[v]=-23333;
            }
        }
        return li-used;
    }
    void prepare(){
        n=read();m=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++)map[i][j]=read();
        
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++)cnt1++,id[i][j]=cnt1;
        T=cnt1+1000;
        for(int i=1;i<=n;i++)if(!v[a[i]]){
            cnt1++;idw[a[i]]=cnt1;
            add(cnt1,T,m*a[i]*a[i]);v[a[i]]=1;
        }
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++){
                if(i==j){
                    map[i][j]-=a[i];
                    add(id[i][j],idw[a[i]],INT);
                }
                else {
                    add(id[i][j],id[i][j-1],INT);
                    add(id[i][j],id[i+1][j],INT);
                }
                if(map[i][j]<0){
                    add(id[i][j],T,-map[i][j]);
                }
                else {
                    add(S,id[i][j],map[i][j]);
                    ans+=map[i][j];
                }
            }
    }
    void dinic(){
        while(bfs()){
            ans-=dfs(S,INT);
        }
    }
    int main(){
        prepare();
        dinic();
        cout<<ans;
        return 0;
    }
    Kiana吃寿司

    by:s_a_b_e_r


    省选的时候注意力全在好吃的寿司上w

    一道求最大权闭合子图的题,然而建边很难qwq

    花式建边:

    对于每个取寿司的区间,正的连s,负的连t,边权是区间美味度的绝对值

    每个单独的寿司连边的时候额外减去这个寿司的编号(因为要算花费)

    每个寿司和这个寿司的编号连一条边,边权INF

    每个编号向t连一条边,边权是m*x2

    然后跑一遍最大流求出最大权闭合子图就好啦

    不会求最大权闭合子图的看这

    ……以及要明确每个数组的范围qwq

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int N=109*109,inf=1e7+7;
    int n,m,cnt=1,p[80000],sum,a[1000+233],tot=1001;
    int s=0,t=70000,dis[80000],d[233][233],num[233][233];
    bool vis[1233];
    struct edge{int to,nex,val;}e[20000<<2];
    void add(int u,int v,int w)
    {
        e[++cnt]=(edge){v,p[u],w};
        p[u]=cnt;
        e[++cnt]=(edge){u,p[v],0};
        p[v]=cnt;
    }
    queue<int>q;
    bool bfs()
    {
        memset(dis,-1,sizeof(dis));
        while(!q.empty())q.pop();
        dis[s]=0;q.push(s);
        while(!q.empty())
        {
            int x=q.front();q.pop();
            for(int i=p[x];i;i=e[i].nex)
            {
                int v=e[i].to;
                if(dis[v]<0&&e[i].val)
                {
                    dis[v]=dis[x]+1;
                    if(v==t)return 1;
                    q.push(v);
                }
            }
        }
        return 0;
    }
    int dfs(int x,int li)
    {
        if(x==t)return li;
        int used=li;
        for(int i=p[x];i;i=e[i].nex)
        {
            int v=e[i].to;
            if(dis[v]==dis[x]+1&&used&&e[i].val)
            {
                int re=dfs(v,min(used,e[i].val));
                if(!re)dis[v]=-1;
                used-=re;
                e[i].val-=re;
                e[i^1].val+=re;
            }
        }
        return li-used;
    }
    int dinic()
    {
        int ans=0;
        while(bfs()){ans+=dfs(s,inf);}
        return ans;
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            if(vis[a[i]])continue;
            vis[a[i]]=1;add(a[i],t,m*a[i]*a[i]);
        }
        for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
        {
            scanf("%d",&d[i][j]);
            num[i][j]=++tot;
        }
        for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
        {
            if(i==j){
                d[i][j]-=a[i];
                add(num[i][j],a[i],inf);
            }
            else{
                add(num[i][j],num[i][j-1],inf);
                add(num[i][j],num[i+1][j],inf);
            }
            if(d[i][j]>=0){add(s,num[i][j],d[i][j]);sum+=d[i][j];}
            else add(num[i][j],t,-d[i][j]);
        }
        cout<<sum-dinic();
        return 0;
    }
    寿司餐厅

    by:wypx


  • 相关阅读:
    UVA 11235 Frequent Values ---RMQ
    UVA 12266 Stock prices --优先队列
    HDU 1896 Stones --优先队列+搜索
    POJ 1442 Black Box -优先队列
    POJ 2263 Heavy Cargo 多种解法
    POJ 3250 Bad Hair Day --单调栈(单调队列?)
    FZU1894 志愿者选拔 --单调队列
    POJ 2823 Sliding Window 再探单调队列
    UVA 11992 Fast Matrix Operations (二维线段树)
    两道相似KMP题
  • 原文地址:https://www.cnblogs.com/ck666/p/7628715.html
一二三 - 开发者的网上家园