数字梯形问题(网络流24题-费用流)

题目链接

https://www.luogu.org/problem/P4013

题目大意

给定一个由 n 行数字组成的数字梯形。

梯形的第一行有 m 个数字。从梯形的顶部的 m个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

1.从梯形的顶至底的 m 条路径互不相交;

2.从梯形的顶至底的 m 条路径仅在数字结点处相交;

3.从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。

解题思路

最小费用最大流,流量用来限制,费用用来统计答案。

对于第一问

把一个点拆成入点和出点,从入点到出点连一条容量1,费用0的边,表示每个点最多只能经过一次。

从S连向第一层的各点的入点,容量1,费用0。

从最后一层点的出点连向T,容量1,费用为负的目标点点权。

从各个点的出点连向下次能到达点的入点,容量1,费用为负的目标点点权。

拆点保证点只经过一次,各边的容量1保证边只经过一次。

对于第二问

在第一问的基础上,将拆点间的容量改为无穷,表示可以重复选择一个点。

从最后一层点的出点连向T,容量inf,费用负的点权。

对于第三问

在第二问的基础上,除了S连向第一层的边之外,把其余边的容量改为inf。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e3+100;
struct node {
    int next,len,w,to;
} edge[2*maxn];

int head[maxn],cnt,dis[maxn*2],flow[2*maxn],vis[2*maxn],pre[2*maxn],
    last[2*maxn],a[maxn];
int maxflow,mincost;
int mp[300][300],w[maxn];
void addedge(int u,int v,int len,int w) {
    edge[cnt].to=v;
    edge[cnt].len=len;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].len=0;
    edge[cnt].w=-w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

bool spfa(int s,int t) {
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    vis[s]=1;
    dis[s]=0;
    pre[t]=-1;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=head[now]; i!=-1; i=edge[i].next) {
            int v = edge[i].to;
            if(edge[i].len>0&&dis[v]>dis[now]+edge[i].w) {
                dis[v]=dis[now]+edge[i].w;
                pre[v]=now;
                last[v]=i;
                flow[v]=min(flow[now],edge[i].len);
                if(!vis[v]) {
                    vis[v]=1;
                    q.push(edge[i].to);
                }
            }
        }
    }
    return pre[t]!=-1;
}

void mcmf(int s,int t) {
    while(spfa(s,t)) {
        int now=t;
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        while(now!=s) {
            edge[last[now]].len-=flow[t];
            edge[last[now]^1].len+=flow[t];
            now=pre[now];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    memset(head,-1,sizeof(head));
    int n,m,s,t;
    cin>>m>>n;
    s=0;//起点
    int ccnt=0,mm=m;
    for(int i=0; i<n; i++) {
        for(int j=0; j<mm; j++) {
            ++ccnt;
            cin>>w[ccnt];
            mp[i][j]=ccnt;
        }
        mm++;
    }
    t=ccnt*2+1;//终点
    //建边
    cnt=0;
    mm=m;
    for(int i=0; i<n; i++) {
        for(int j=0; j<mm; j++) {
            addedge(mp[i][j],mp[i][j]+ccnt,1,0);
            if(i==0) {
                addedge(s,mp[i][j],1,0);
            }
            if(i==n-1) {
                addedge(mp[i][j]+ccnt,t,1,-w[mp[i][j]]);
            } else {
                addedge(mp[i][j]+ccnt,mp[i+1][j],1,-w[mp[i][j]]);
                addedge(mp[i][j]+ccnt,mp[i+1][j+1],1,-w[mp[i][j]]);
            }
        }
        mm++;
    }
    mcmf(s,t);
    cout<<-mincost<<endl;


    memset(head,-1,sizeof(head));
    cnt=0;
    mm=m;
    maxflow=0;
    mincost=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<mm; j++) {
            addedge(mp[i][j],mp[i][j]+ccnt,0x3f3f3f3f,0);
            if(i==0) {
                addedge(s,mp[i][j],1,0);
            }
            if(i==n-1) {
                addedge(mp[i][j]+ccnt,t,0x3f3f3f3f,-w[mp[i][j]]);
            } else {
                addedge(mp[i][j]+ccnt,mp[i+1][j],1,-w[mp[i][j]]);
                addedge(mp[i][j]+ccnt,mp[i+1][j+1],1,-w[mp[i][j]]);
            }
        }
        mm++;
    }
    mcmf(s,t);
    cout<<-mincost<<endl;


    memset(head,-1,sizeof(head));
    cnt=0;
    mm=m;
    maxflow=0;
    mincost=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<mm; j++) {
            addedge(mp[i][j],mp[i][j]+ccnt,0x3f3f3f3f,0);
            if(i==0) {
                addedge(s,mp[i][j],1,0);
            }
            if(i==n-1) {
                addedge(mp[i][j]+ccnt,t,0x3f3f3f3f,-w[mp[i][j]]);
            } else {
                addedge(mp[i][j]+ccnt,mp[i+1][j],0x3f3f3f3f,-w[mp[i][j]]);
                addedge(mp[i][j]+ccnt,mp[i+1][j+1],0x3f3f3f3f,-w[mp[i][j]]);
            }
        }
        mm++;
    }
    mcmf(s,t);
    cout<<-mincost<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注