【网络流24题】【LOJ6010】数字梯形（费用流）

problem

• 给定一个n行的数字梯形，第一行有m个数字
• 从第一行的每个数字开始往左下或右下移动到底，累加路径上的值
• 求数字总和最大。

满足限制：
1、路径互不相交
2、路径仅在数字结点处相交
3、路径随意相交

solution

对于3个限制：
1、拆点，费用流
2、限制边, 费用流
3、费用流

注意数组记得开大，，，是n行，不是n个。。。

codes

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

const int N = 1100*2+10, M = 100000+10, inf = 1<<30;

//Grape
struct Edge{
    int from, to, cap, flow, cost;
}e[M];
int tot=1, head[N], Next[M];
void AddEdge(int u, int v, int w, int c){
    //正向边，初始容量w，单位费用c
    e[++tot].from = u, e[tot].to = v, e[tot].cap = w, e[tot].flow = 0, e[tot].cost = c;
    Next[tot] = head[u], head[u] = tot;
    //反向边，初始容量0，单位费用-c，与正向边成对存储
    e[++tot].from = v, e[tot].to = u, e[tot].cap = 0, e[tot].flow = 0, e[tot].cost = -c;
    Next[tot] = head[v], head[v] = tot;
}

//Cost flow
int s, t, incf[N], pre[N];
int dist[N], vis[N];
bool spfa(int &fl, int &cst){
    //spfa
    queue<int>q;
    memset(dist,0xcf,sizeof(dist));//-inf
    memset(vis,0,sizeof(vis));
    q.push(s); dist[s]=0; vis[s]=1;
    incf[s] = 1<<30; //到s为止的增广路上各边的最小的剩余容量
    while(q.size()){
        int x = q.front(); q.pop(); vis[x] = 0;
        for(int i = head[x]; i; i = Next[i]){
            if(e[i].flow==e[i].cap)continue; //剩余容量为0，不再残量网络中，不遍历
            int y = e[i].to;
            if(dist[y]<dist[x]+e[i].cost){
                dist[y] = dist[x]+e[i].cost;
                incf[y] = min(incf[x], e[i].cap-e[i].flow);
                pre[y] = i;//记录前驱，用于找方案
                if(!vis[y])vis[y]=1, q.push(y);
            }
        }
    }
    if(dist[t] == 0xcfcfcfcf)return false;//汇点不可达，已求出最大流
    //update
    int x = t;
    while(x != s){
        int i = pre[x];
        e[i].flow += incf[t];
        e[i^1].flow -= incf[t];
        x = e[i].from;
    }
    fl += incf[t];
    cst += dist[t]*incf[t];
    return true;
}
int maxflow(){
    int flow = 0, cost = 0;
    while(spfa(flow, cost));//,,,,,,
    return cost;
}

//Timu
int n, m, a[110][110];
void input(){
    cin>>m>>n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i+m-1; j++)
            cin>>a[i][j];
}
int code(int i, int j){
    return (m+m+i-2)*(i-1)/2+j;//梯形面积公式，一共这么多点。
}
void task1(){
    int num = code(n,n+m-1);//原先一共有这么多点
    s = 0, t = num*2+1;
    for(int i = 1; i <= m; i++)
        AddEdge(s,i,1,0);
    for(int i = 1; i <= n+m-1; i++)
        AddEdge(num+code(n,i),t,1,0);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m+i-1; j++){
            AddEdge(code(i,j),num+code(i,j),1,a[i][j]);
            if(i < n){
                AddEdge(num+code(i,j),code(i+1,j),1,0);
                AddEdge(num+code(i,j),code(i+1,j+1),1,0);
            }
        }
    }
    cout<<maxflow()<<'\n';
}
void task2(){
    memset(head,0,sizeof(head));
    memset(Next,0,sizeof(Next));
    tot = 1;
    for(int i = 1; i <= m; i++)
        AddEdge(s,i,1,0);
    for(int i = 1; i <= n+m-1; i++)
        AddEdge(code(n,i),t,inf,a[n][i]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i+m-1; j++){
            if(i < n){
                AddEdge(code(i,j),code(i+1,j), 1, a[i][j]);
                AddEdge(code(i,j),code(i+1,j+1), 1, a[i][j]);
            }
        }
    }
    cout<<maxflow()<<'\n';
}
void task3(){
    memset(head,0,sizeof(head));
    memset(Next,0,sizeof(Next));
    tot = 1;
    for(int i = 1; i <= m; i++)
        AddEdge(s,i,1,0);
    for(int i = 1; i <= n+m-1; i++)
        AddEdge(code(n,i),t,inf,a[n][i]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i+m-1; j++){
            if(i < n){
                AddEdge(code(i,j),code(i+1,j), inf, a[i][j]);
                AddEdge(code(i,j),code(i+1,j+1), inf, a[i][j]);
            }
        }
    }
    cout<<maxflow()<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    input();
    task1();
    task2();
    task3();
    return 0;
}
  

 

  
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
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80657398