「网络流 24 题」数字梯形 最大费用最大流

Posted on | In , ,

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

分别遵守以下规则：

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

题目链接

Trick: 汇点T设错了大小，自闭了一个小时。

题解

  • 规则1：S到顶层的每个点连一条容量为1，费用为0的边，对每个点 $i$ 拆点为 $i’$，其建边费用为点权容量为1，每个点转移到下面的点对(i,j)，$i’$到$j$容量为1费用为0，最后底层每个点$i’$到$T$建容量为1费用0的边即可。
  • 规则2：不用拆点了，层与层之间建容量为1边权为点权的边即可
  • 规则3：同规则2，层与层之间建容量为无穷大边权为点权的边即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1610;
const int INF=1e9+7;

int n, m, mp[maxn][maxn], num[maxn], id[maxn][maxn], rid[maxn][maxn];


struct Edge
{
    int from, to, cap, flow, cost;
    Edge(int u,int v,int c,int f, int w):from(u), to(v), cap(c), flow(f), cost(w) {}
};

struct MCMF
{
    int n, m;
    vector<Edge> edges;   // 边数的两倍
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    int inq[maxn];        // 是否在队列中
    int d[maxn];          // Bellman-Ford
    int a[maxn];          // 当起点到i的可改流量
    int p[maxn];          // 最短路树上p的入弧编号(path路径)

    void init(int n)
    {
        this->n = n;
        for(int i=0; i<=n+1; i++)
            G[i].clear();
        edges.clear();
    }

    void Addedge(int from, int to, int cap,int cost)
    {
        edges.push_back(Edge(from, to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BellmanFord(int s,int t,int& flow, long long& cost)
    {
        for(int i=0; i<=n; i++)
            d[i] = 1000000000+2;
        memset(inq, 0, sizeof(inq));
        d[s]=0; inq[s]=1; p[s]=0; a[s]=1000000000+2;

        queue<int> Q;
        Q.push(s);

        while(!Q.empty())
        {
          //  cout<<123<<endl;
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0; i<G[u].size(); i++)
            {
                Edge& e=edges[G[u][i]];
                if( e.cap > e.flow && d[e.to] > d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap-e.flow);
                    if(!inq[e.to]){ Q.push(e.to); inq[e.to]=1;}
                }
            }
        }
        if(d[t] == 1000000000+2)
            return false;
        flow += a[t];
        cost += (long long)d[t] * (long long)a[t];
        for(int u=t; u!=s; u=edges[p[u]].from)
        {
            edges[p[u]].flow += a[t];
            edges[p[u]^1].flow -= a[t];
        }
        return true;
    }

    void MincostMaxflow(int s,int t,long long& cost)
    {
        int flow=0; cost=0;
        while(BellmanFord(s, t, flow, cost));
       // return flow;
    }
};

MCMF now1, now2, now3;

int main()
{
    scanf("%d%d", &m, &n);

    int st=0, ed=maxn-2;
    cout<<ed<<endl;
    now1.init(ed);
    for(int i=1;i<=n;i++)
    {
        num[i]=m;
        for(int j=1;j<=m;j++)
        {
            scanf("%d", &mp[i][j]);
        }
        ++m;
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=num[i];j++)
        {
            id[i][j]=++cnt;
            rid[i][j]=++cnt;
        }
    }
    cout<<cnt<<endl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=num[i];j++)
        {
            now1.Addedge(id[i][j], rid[i][j], 1, -mp[i][j]);
            if(i==1)
            {
                now1.Addedge(st, id[i][j], 1, 0);
            }
            if(i!=n)
            {
                now1.Addedge(rid[i][j], id[i+1][j], 1, 0);
                now1.Addedge(rid[i][j], id[i+1][j+1], 1, 0);
            }
            if(i==n)
            {
                now1.Addedge(rid[i][j], ed, 1, 0);
            }
        }
    }
   // cout<<123<<endl;
    ll  ans1;
    now1.MincostMaxflow(st, ed, ans1);
    ans1=-ans1;
    now2.init(ed);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=num[i];j++)
        {
           // now2.Addedge(id[i][j], rid[i][j], INF, -mp[i][j]);
            if(i==1)
            {
                now2.Addedge(st, id[i][j], 1, 0);
            }
            if(i!=n)
            {
                now2.Addedge(id[i][j], id[i+1][j], 1, -mp[i][j]);
                now2.Addedge(id[i][j], id[i+1][j+1], 1, -mp[i][j]);
            }
            if(i==n)
            {
                now2.Addedge(id[i][j], ed, INF, -mp[i][j]);
            }
        }
    }
    ll  ans2;
    now2.MincostMaxflow(st, ed, ans2);
    ans2=-ans2;

    now3.init(ed);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=num[i];j++)
        {
           // now2.Addedge(id[i][j], rid[i][j], INF, -mp[i][j]);
            if(i==1)
            {
                now3.Addedge(st, id[i][j], 1, 0);
            }
            if(i!=n)
            {
                now3.Addedge(id[i][j], id[i+1][j], INF, -mp[i][j]);
                now3.Addedge(id[i][j], id[i+1][j+1], INF, -mp[i][j]);
            }
            if(i==n)
            {
                now3.Addedge(id[i][j], ed, INF, -mp[i][j]);
            }
        }
    }
    ll  ans3;
    now3.MincostMaxflow(st, ed, ans3);
    ans3=-ans3;
    printf("%lld\n%lld\n%lld\n", ans1, ans2, ans3);
}