网络流24题之十六 数字梯形问题

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

66
75
77

模型

求图的最大权不相交路径及其变种，用费用最大流解决。

实现

规则(1)

把梯形中每个位置抽象为两个点<i.a>,<i.b>，建立附加源S汇T。

1、对于每个点i从<i.a>到<i.b>连接一条容量为1，费用为点i权值的有向边。
2、从S向梯形顶层每个<i.a>连一条容量为1，费用为0的有向边。
3、从梯形底层每个<i.b>向T连一条容量为1，费用为0的有向边。
4、对于每个点i和下面的两个点j，分别连一条从<i.b>到<j.a>容量为1，费用为0的有向边。

求最大费用最大流，费用流值就是结果。

规则(2)

把梯形中每个位置看做一个点i，建立附加源S汇T。

1、从S向梯形顶层每个i连一条容量为1，费用为0的有向边。
2、从梯形底层每个i向T连一条容量为无穷大，费用为0的有向边。
3、对于每个点i和下面的两个点j，分别连一条从i到j容量为1，费用为点i权值的有向边。

求最大费用最大流，费用流值就是结果。

规则(3)

把梯形中每个位置看做一个点i，建立附加源S汇T。

1、从S向梯形顶层每个i连一条容量为1，费用为0的有向边。
2、从梯形底层每个i向T连一条容量为无穷大，费用为0的有向边。
3、对于每个点i和下面的两个点j，分别连一条从i到j容量为无穷大，费用为点i权值的有向边。

求最大费用最大流，费用流值就是结果。

分析

对于规则1，要求路径完全不相交，也就是每个点最多只能被访问了一次，所以要把点拆分，之间连接容量为1的边。因为任意一条ST之间的路径都是一个解，在拆分的点内部的边费用设为点的权值，求最大费用最大流就是费用最大的m条路经。

对于规则2，要求路径可以相交，但不能有重叠，此时可以不必拆点了。为了保证路径没有重叠，需要在相邻的两个点上限制流量为1，由于顶层的每个点只能用1次，S向顶层点流量限制也为1。费用只需设在相邻点的边上，求最大费用最大流即可。

对于规则3，要求路径除了顶层每个点以外可以任意相交重叠。在规则2的基础上，取消除S到顶层顶点之间的边以外所有边的流量限制即可。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <iostream>
#define M 50000
#define N 5000
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
map <string,int>ma;
struct node{int from,to,next,flow,cost;}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
int pe[N],pv[N],dis[N],vis[N];
void add(int x,int y,int z,int zz){
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].cost=zz;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z,int zz){add(x,y,z,zz),add(y,x,0,-zz);}
queue<int>que;
bool spfa(int S,int T)
{
    for (int i=S;i<=T;i++)
        dis[i]=-INF;
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=st[now];~i;i=e[i].next)
            if (e[i].flow>0 && dis[e[i].to]<dis[now]+e[i].cost)
            {
                dis[e[i].to]=dis[now]+e[i].cost;
                pe[e[i].to]=i,pv[e[i].to]=now;
                if (!vis[e[i].to])
                    vis[e[i].to]=1,que.push(e[i].to);
            }
    }
    return dis[T]!=-INF;
}
Pair mfmc(int S,int T)
{
    int COST=0,FLOW=0,flow;
    while(spfa(S,T))
    {
        flow=0x3f3f3f3f;
        for (int i=T;i!=S;i=pv[i])
            flow=min(flow,e[pe[i]].flow);
        COST+=flow*dis[T];
        FLOW+=flow;
        for (int i=T;i!=S;i=pv[i])
            e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
    }
    return make_pair(FLOW,COST);
}
main()
{
    static int m,sum=0,id[N][N],val[N];
    scanf("%d%d",&m,&n);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    for(int i=1;i<=n;i++)
        for (int j=1;j<=m+i-1;j++)
            scanf("%d",&val[++sum]),id[i][j]=sum;
    int S=0,T=sum+sum+1;
    //solve1
    for (int i=1;i<=sum;i++)
        add_edge(i,i+sum,1,val[i]);
    for (int i=1;i<=m;i++)
        add_edge(S,id[1][i],1,0);
    for (int i=1;i<=n+m-1;i++)
        add_edge(id[n][i]+sum,T,1,0);
    for (int i=1;i<n;i++)
        for (int j=1;j<=i+m-1;j++)
            add_edge(id[i][j]+sum,id[i+1][j],1,0),
            add_edge(id[i][j]+sum,id[i+1][j+1],1,0);
    Pair ans=mfmc(S,T);
    printf("%d\n",ans.second);
    //solve2
    memset(st,-1,sizeof st);
    memset(e,-1,sizeof e);
    S=0,T=sum+1;
    for (int i=1;i<=m;i++)
        add_edge(S,id[1][i],1,0);
    for (int i=1;i<=n+m-1;i++)
        add_edge(id[n][i],T,INF,val[id[n][i]]);
    for (int i=1;i<n;i++)
        for (int j=1;j<=i+m-1;j++)
            add_edge(id[i][j],id[i+1][j],1,val[id[i][j]]),
            add_edge(id[i][j],id[i+1][j+1],1,val[id[i][j]]);
    ans=mfmc(S,T);
    printf("%d\n",ans.second);
    //solve3
    memset(st,-1,sizeof st);
    memset(e,-1,sizeof e);
    S=0,T=sum+1;
    for (int i=1;i<=m;i++)
        add_edge(S,id[1][i],1,0);
    for (int i=1;i<=n+m-1;i++)
        add_edge(id[n][i],T,INF,val[id[n][i]]);
    for (int i=1;i<n;i++)
        for (int j=1;j<=i+m-1;j++)
            add_edge(id[i][j],id[i+1][j],INF,val[id[i][j]]),
            add_edge(id[i][j],id[i+1][j+1],INF,val[id[i][j]]);
    ans=mfmc(S,T);
    printf("%d\n",ans.second);
}