P4013 数字梯形问题

佚名 6年前 (2019-04-15) 随笔 478人围观抢沙发百度已收录

网络流24题其中一题。懒癌发作了，洛谷有许多题解，这里就不说了。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

为了少写点代码，这里建图单独写了个子程序。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N=5000+10;
const int M=50000+10;
const int INF=0x3f3f3f3f;
int n,m,bs,s,t,maxflow,mincost;
struct edge{
    int nxt,to,cap,cost;
}edges[M<<1];
int cnt=1,head[N],pre[N],mp[50][50];

void add_edge(int x,int y,int z,int c) {
    edges[++cnt].nxt=head[x]; edges[cnt].to=y; edges[cnt].cap=z; edges[cnt].cost=c; head[x]=cnt;
}

queue<int> q;
int dis[N],lim[N]; 
bool inq[N];
bool spfa(int s,int t) {
    while (!q.empty()) q.pop();
    memset(dis,0x3f,sizeof(dis));
    memset(inq,0,sizeof(inq));
    dis[s]=0; inq[s]=1; lim[s]=INF; q.push(s);
    while (!q.empty()) {
        int x=q.front(); q.pop();
        for (int i=head[x];i;i=edges[i].nxt) {
            edge e=edges[i];
            if (e.cap && dis[x]+e.cost<dis[e.to]) {
                dis[e.to]=dis[x]+e.cost;
                pre[e.to]=i;  //即e.to这个点是从i这条边来的 
                lim[e.to]=min(lim[x],e.cap);
                if (!inq[e.to]) { q.push(e.to); inq[e.to]=1; }
            }
        }
        inq[x]=0;
    }
    return !(dis[t]==INF); 
}

void MCMF() {
    maxflow=0; mincost=0;
    while (spfa(s,t)) {
        int now=t;
        maxflow+=lim[t];
        mincost+=lim[t]*dis[t];
        while (now!=s) {
            edges[pre[now]].cap-=lim[t];
            edges[pre[now]^1].cap+=lim[t];
            now=edges[pre[now]^1].to;
        }
    }
}

int id(int x,int y) { return (x-1)*(m+n)+y; }

void build(int t1,int t2) {  //分别是点限制和边限制 
    cnt=1; memset(head,0,sizeof(head));
    s=0; t=2*(m+n)*(m+n)+1; bs=(m+n)*(m+n);
    for (int i=1;i<=m;i++) add_edge(s,id(1,i),1,0),add_edge(id(1,i),s,0,0);
    for (int i=1;i<=n+m-1;i++) add_edge(id(n,i)+bs,t,INF,0),add_edge(t,id(n,i)+bs,0,0);
    for (int i=1;i<n;i++)
        for (int j=1;j<=m+i-1;j++) {
            add_edge(id(i,j)+bs,id(i+1,j),t2,0);
            add_edge(id(i+1,j),id(i,j)+bs,0,0);
            add_edge(id(i,j)+bs,id(i+1,j+1),t2,0);
            add_edge(id(i+1,j+1),id(i,j)+bs,0,0);
        }
    for (int i=1;i<=n;i++) for (int j=1;j<=m+i-1;j++) add_edge(id(i,j),id(i,j)+bs,t1,-mp[i][j]),add_edge(id(i,j)+bs,id(i,j),0,mp[i][j]);    
}

int main()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;i++) for (int j=1;j<=m+i-1;j++) scanf("%d",&mp[i][j]); 
    
    build(1,1); MCMF(); cout<<-mincost<<endl;
    build(INF,1); MCMF(); cout<<-mincost<<endl;
    build(INF,INF); MCMF(); cout<<-mincost<<endl;
    return 0;
}