#6010. 「网络流 24 题」数字梯形

题目描述

给定一个由 n nn 行数字组成的数字梯形如下图所示。梯形的第一行有 m mm 个数字。从梯形的顶部的 m mm 个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。

分别遵守以下规则：

从梯形的顶至底的 m mm 条路径互不相交；
从梯形的顶至底的 m mm 条路径仅在数字结点处相交；
从梯形的顶至底的 m mm 条路径允许在数字结点相交或边相交。

输入格式

第 1 11 行中有 2 22 个正整数 m mm 和 n nn，分别表示数字梯形的第一行有 m mm 个数字，共有 n nn 行。接下来的 n nn 行是数字梯形中各行的数字。
第 1 11 行有 m mm 个数字，第 2 22 行有 m+1 m + 1m+1 个数字 ……

输出格式

将按照规则 1，规则 2，和规则 3 计算出的最大数字总和并输出，每行一个最大总和。

样例

样例输入

2 5

2 3

3 4 5

9 10 9 1

1 1 10 1 1

1 1 10 12 1 1

样例输出

数据范围与提示

1≤m,n≤20 1 \leq m, n \leq 201≤m,n≤20

code

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N = ;

 const int INF = 1e9;

 struct Edge{

     int u,v,f,c,nxt;

     Edge(){}

     Edge(int a,int b,int flow,int cost,int nt) {

         u = a;v = b;f = flow;c = cost;nxt = nt;

     }

 }e[];

 int head[N],dis[N],q[],pre[N],a[][],b[][];

 bool vis[N];

 int n,m,S,T,tn,L,R,Mc,ans,tot;

 inline char nc() {

     static char buf[],*p1 = buf,*p2 = buf;

     return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2) ? EOF :*p1++;

 }

 inline int read() {

     int x = ,f = ;char ch=nc();

     for (; ch<''||ch>''; ch=nc()) if(ch=='-')f=-;

     for (; ch>=''&&ch<=''; ch=nc()) x=x*+ch-'';

     return x*f;

 }

 void add_edge(int u,int v,int f,int c) {

     e[++tot] = Edge(u,v,f,c,head[u]);head[u] = tot;

     e[++tot] = Edge(v,u,,-c,head[v]);head[v] = tot;

 }

 bool spfa() {

     for (int i=; i<=T; ++i) vis[i]=false,dis[i]=INF;

     L = ;R = ;

     dis[S] = ;

     q[++R] = S;vis[S] = true;pre[S] = ;

     while (L <= R) {

         int u = q[L++];

         for (int i=head[u]; i; i=e[i].nxt) {

             int v = e[i].v;

             if (dis[v]>dis[u]+e[i].c && e[i].f > ) {

                 dis[v] = dis[u] + e[i].c;

                 pre[v] = i;

                 if (!vis[v]) q[++R] = v,vis[v] = true;

             }

         }

         vis[u] = false;

     }

     return dis[T]!=INF;

 }

 void mcf() {

     int zf = INF;

     for (int i=T; i!=S; i=e[pre[i]].u)

         zf = min(zf,e[pre[i]].f);

     for (int i=T; i!=S; i=e[pre[i]].u)

         e[pre[i]].f -= zf,e[pre[i]^].f += zf;

     Mc += dis[T]*zf;

 }

 int work() {

     Mc = ;

     while (spfa()) mcf();

     printf("%d\n",-Mc);

 }

 void init() {

     tot = ;

     memset(head,,sizeof(head));

 }

 void build_1() {

     init();

     S = tn + tn + ;T = tn + tn + ;

     for (int i=; i<=n; ++i)

         for (int j=; j<=m+i-; ++j) {

             add_edge(b[i][j],b[i][j]+tn,,-a[i][j]);

             add_edge(b[i][j]+tn,b[i+][j],,);

             add_edge(b[i][j]+tn,b[i+][j+],,);

             if (i==) add_edge(S,b[i][j],,);

             if (i==n) add_edge(b[i][j]+tn,T,,);

         }

 }

 void build_2() {

     init();

     S = tn + ;T = tn + ;

     for (int i=; i<=n; ++i) {

         for (int j=; j<=m+i-; ++j) {

             add_edge(b[i][j],b[i+][j],,-a[i][j]);

             add_edge(b[i][j],b[i+][j+],,-a[i][j]);

             if (i==) add_edge(S,b[i][j],,);

             if (i==n) add_edge(b[i][j],T,INF,-a[i][j]);

         }

     }

 }

 void build_3() {

     init();

     S = tn + ;T = tn + ;

     for (int i=; i<=n; ++i) {

         for (int j=; j<=m+i-; ++j) {

             add_edge(b[i][j],b[i+][j],INF,-a[i][j]);

             add_edge(b[i][j],b[i+][j+],INF,-a[i][j]);

             if (i==) add_edge(S,b[i][j],,);

             if (i==n) add_edge(b[i][j],T,INF,-a[i][j]);

         }

     }

 }

 int main() {

     m = read(),n = read();

     for (int i=; i<=n; ++i)

         for (int j=; j<=m+i-; ++j) a[i][j] = read(),b[i][j] = ++tn;

     build_1();work();

     build_2();work();

     build_3();work();

     return ;

 }

巴特西

LOJ #6010. 「网络流 24 题」数字梯形