洛谷 P4013 数字梯形问题 题解 【网络流】【费用流】

作者: wjyyy 分类: 网络流,解题报告,费用流 发布时间: 2019-01-15 15:56

点击量:26

是一道模板性质的题。

题目描述

给定一个由\(n\)行数字组成的数字梯形如下图所示。梯形的第一行有\(m\)个数字。从梯形的顶部的\(m\)个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

  1. 从梯形的顶至底的\(m\)条路径互不相交;
  2. 从梯形的顶至底的\(m\)条路径仅在数字结点处相交;
  3. 从梯形的顶至底的\(m\)条路径允许在数字结点相交或边相交。

输入输出格式

输入格式:

第\(1\)行中有\(2\)个正整数\(m\)和\(n\),分别表示数字梯形的第一行有\(m\)个数字,共有\(n\)行。接下来的\(n\)行是数字梯形中各行的数字。

第\(1\)行有\(m\)个数字,第\(2\)行有\(m+1\)个数字 ……

输出格式:

将按照规则 1,规则 2,和规则 3 计算出的最大数字总和并输出,每行一个最大总和。

输入输出样例

输入样例#1:

2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1

输出样例#1:

66
75
77

说明

\(1\le m,n\le 20\)

题解:

做这道题的时候想到了P4066 [SHOI2003]吃豆豆
这个题,我们先针对问题1,2,3分别进行分析。

  1. 互不相交,也就是每个数只能经过一次,更不用说边了。此时把每个数拆成两个点\(a_1,a_2\),\(a_1\to a_2\)的边容量为\(1\),边权为这个数的大小。
  2. 仅在点处相交,也就是说点可以多次经过,上述\(a_1\to a_2\)的容量可以变为\(inf\)。
  3. 边点均可相交,裸的最长路。把上面的约束条件全部去掉,只要向左下或右下走就合法,除了超级源点流出到第一行的边为\(1\),其余都设为\(\inf\)。

然后把边权取反,跑最小费用最大流。再把答案取反输出即可。

Code:

#include<cstdio>
#include<cstring>
#include<queue>
using std::queue;
int pos[25][45],pre[2000],dis[2000];
bool used[2000];
int f[2000][2000],g[2000][2000],a[25][45],w[2000][2000];
bool spfa()
{
    memset(used,0,sizeof(used));
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    dis[0]=0;
    used[0]=1;
    q.push(0);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        used[x]=0;
        for(int i=0;i<=1666;++i)
            if(f[x][i]&&dis[i]>dis[x]+w[x][i])
            {
                dis[i]=dis[x]+w[x][i];
                pre[i]=x;
                if(!used[i])
                {
                    used[i]=1;
                    q.push(i);
                }
            }
    }
    return dis[1666]!=0x3f3f3f3f;
}
int flow()
{
    for(int i=0;i<=1666;++i)
        for(int j=0;j<=1666;++j)
            f[i][j]=g[i][j];
    int ans=0;
    while(spfa())
    {
        int p=1666,mn=0x3fffffff;
        while(p)
        {
            mn=mn<f[pre[p]][p]?mn:f[pre[p]][p];
            p=pre[p];
        }
        p=1666;
        while(p)
        {
            f[pre[p]][p]-=mn;
            f[p][pre[p]]+=mn;
            ans+=mn*w[pre[p]][p];
            p=pre[p];
        }
    }
    return -ans;
}
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=21;++i)
        for(int j=1;j<=40;++j)
            pos[i][j]=(i-1)*40+j;
    for(int i=1;i<=m;++i)
        g[0][i<<1]=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<m+i;++j)
        {
            scanf("%d",&a[i][j]);
            int t1=pos[i+1][j]<<1,t2=pos[i+1][j+1]<<1,t=pos[i][j]<<1|1;
            g[t][t1]=1;
            g[t][t2]=1;
        }

    for(int i=1;i<m+n;++i)
        g[pos[n][i]<<1|1][1666]=0x3fffffff;
    for(int i=1;i<=n;++i)
        for(int j=1;j<m+i;++j)
        {
            int t1=pos[i][j]<<1;
            int t2=pos[i][j]<<1|1;
            g[t1][t2]=1;
            w[t1][t2]=-a[i][j];
            w[t2][t1]=a[i][j];
        }
    printf("%d\n",flow());
    for(int i=1;i<=n;++i)
        for(int j=1;j<m+i;++j)
        {
            int t1=pos[i][j]<<1;
            int t2=pos[i][j]<<1|1;
            g[t1][t2]=0x3fffffff;
        }
    printf("%d\n",flow());
    for(int i=1;i<=n;++i)
        for(int j=1;j<m+i;++j)
        {
            int t1=pos[i+1][j]<<1,t2=pos[i+1][j+1]<<1,t=pos[i][j]<<1|1;
            g[t][t1]=0x3fffffff;
            g[t][t2]=0x3fffffff;
        }
    printf("%d\n",flow());
    return 0;
}

1
说点什么

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

[…] 写一篇题解 […]

/* */