做题记录：P4013 数字梯形问题

首先这题是最大费用最大流。

然后几乎没什么细节好主意的。

遵守以下规则：

• 梯形的第一行有 mm 个数字。

• 从梯形的顶部的 mm 个数字开始

• 在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。

scanf("%lld%lld",&m,&n);
s=1e6,t=1e6+1;//p[i][j]为点(i,j)的编号。
for(int i=1;i<=n;i++){
    for(int j=1;j<=m+i-1;j++)scanf("%lld",&a[i][j]),p[i][j]=++bh;   
}

另外有三条选择规则：

• 从梯形的顶至底的 mm 条路径互不相交；

• 从梯形的顶至底的 mm 条路径仅在数字结点处相交；

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

求出三种规则下的最大数值。

第一种路径互不相交，我们就把边流量设为 11 ,这样限制通过一次。

把每个点拆成两个点，进行分层图，避免重复走。

再连接原点和汇点，注意原点流出只有一个，所以流量为 11 ,汇点则是很多个，所以流量是无穷大。

for(int i=1;i<=m;i++)add(s,p[1][i],1,0);
for(int i=1;i<n;i++){
    for(int j=1;j<=m+i-1;j++){
        add(p[i][j],p[i][j]+bh,1,a[i][j]);
        add(p[i][j]+bh,p[i+1][j],1,0);
        add(p[i][j]+bh,p[i+1][j+1],1,0);
    }
}
for(int i=1;i<=n+m-1;i++){
    add(p[n][i],p[n][i]+bh,inf,a[n][i]);
    add(p[n][i]+bh,t,1,0);
}

第二种不用拆点，直接连接。

第三种和第二种相同，只是边珂以无数次经过，于是把边流量设为无穷大。

代码不算特别长，但是比正常的题目长很多，119行。

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#define N 1919810 
using namespace std;
int head[N],to[N],nxt[N],val[N],cst[N],tot=1,n,m,s,t;
int d[N],a[114][114],ansc,p[114][114],bh,ne=1e4;
bool vis[N];
void add(int u,int v,int w,int c){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
    val[tot]=w;
    cst[tot]=c;
    to[++tot]=u;
    nxt[tot]=head[v];
    head[v]=tot;
    val[tot]=0;
    cst[tot]=-c;
} 
void clear(){
    memset(head,0,sizeof(head));
    memset(d,0,sizeof(d));
    tot=1;ansc=0;
}
bool spfa(){
    queue<int>q;
    memset(vis,0,sizeof(vis));
    memset(d,128,sizeof(d));
    q.push(s);int wxx=d[0];
    d[s]=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            if(!val[i])continue;
            int y=to[i],w=cst[i];
            if(d[y]<d[x]+w){
                d[y]=d[x]+w;
                if(!vis[y])vis[y]=1,q.push(y);
            }
        }
    }
    return d[t]>wxx;
}
int dfs(int x,int a){
    if(!a||x==t)return a;
    int res=a;vis[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(val[i]&&!vis[y]&&d[y]==d[x]+cst[i]){
            int tmp=dfs(y,min(val[i],res));
            res-=tmp;
            val[i]-=tmp;
            val[i^1]+=tmp;
            ansc+=tmp*cst[i];
            if(res<=0){
                vis[x]=0;
                return a;
            }
        }
    }
    vis[x]=0;
    if(res==a)vis[x]=1;
    return a-res;
}
void dinic(){
    while(spfa()){
        memset(vis,0,sizeof(vis));
        while(dfs(s,inf));
    }
}
signed main(){
    scanf("%lld%lld",&m,&n);
    s=1e6,t=1e6+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m+i-1;j++)scanf("%lld",&a[i][j]),p[i][j]=++bh;   
    }
    for(int i=1;i<=m;i++)add(s,p[1][i],1,0);
    for(int i=1;i<n;i++){
        for(int j=1;j<=m+i-1;j++){
            add(p[i][j],p[i][j]+bh,1,a[i][j]);
            add(p[i][j]+bh,p[i+1][j],1,0);
            add(p[i][j]+bh,p[i+1][j+1],1,0);
        }
    }
    for(int i=1;i<=n+m-1;i++){
        add(p[n][i],p[n][i]+bh,inf,a[n][i]);
        add(p[n][i]+bh,t,1,0);
    }
    dinic();
    printf("%lld\n",ansc);
    clear();
    for(int i=1;i<=m;i++)add(s,p[1][i],1,0);
    for(int i=1;i<n;i++){
        for(int j=1;j<=m+i-1;j++){
            add(p[i][j],p[i+1][j],1,a[i][j]);
            add(p[i][j],p[i+1][j+1],1,a[i][j]);
        }
    }
    for(int i=1;i<=n+m-1;i++)add(p[n][i],t,inf,a[n][i]);
    dinic();
    printf("%lld\n",ansc);
    clear();
    for(int i=1;i<=m;i++)add(s,p[1][i],1,0);
    for(int i=1;i<n;i++){
        for(int j=1;j<=m+i-1;j++){
            add(p[i][j],p[i+1][j],inf,a[i][j]);
            add(p[i][j],p[i+1][j+1],inf,a[i][j]);
        }
    }
    for(int i=1;i<=n+m-1;i++)add(p[n][i],t,inf,a[n][i]);
    dinic();
    printf("%lld\n",ansc);
    return 0;
}

完结撒花