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

点击量：357

是一道模板性质的题。

目录

题目描述

给定一个由$ 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;
}