四川省安监站网址,汾阳网架公司,青岛城乡建设局网站,自适应wordpress主题Description 设有N*N的方格图#xff0c;我们将其中的某些方格填入正整数#xff0c; 而其他的方格中放入0。 某人从图得左上角出发#xff0c;可以向下走#xff0c;也可以向右走#xff0c;直到到达右下角。 在走过的路上#xff0c;他取走了方格中的数。#xff08;取… Description 设有N*N的方格图我们将其中的某些方格填入正整数 而其他的方格中放入0。 某人从图得左上角出发可以向下走也可以向右走直到到达右下角。 在走过的路上他取走了方格中的数。取走后方格中数字变为0 此人从左上角到右下角共走3次试找出3条路径使得取得的数总和最大。 Input 第一行:N (4N20) 接下来一个N*N的矩阵矩阵中每个元素不超过80不小于0 Output 一行表示最大的总和。 Sample Input 4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4 Sample Output 39 题解转载 -原文地址- $DP$好题。 这里给出费用流的做法: 拆点建图每一个点都拆成两个点在这里就称为出点和入点。 出点和入点建两条边一条费用为$s[i][j]$流量为$1$一条费用为$0$流量为$inf$。分别表示选择这个点和从这个点上经过 将$(i,j)$的出点分别和$(i1,j)$$(i,j1)$的入点建边流量为$inf$费用为$0$。表示行进 跑一边最大费用最大流就可以了。 1 #include set2 #include map3 #include ctime4 #include cmath5 #include queue6 #include stack7 #include vector8 #include cstdio9 #include string
10 #include cstring
11 #include cstdlib
12 #include iostream
13 #include algorithm
14 #define LL long long
15 #define Max(a, b) ((a) (b) ? (a) : (b))
16 #define Min(a, b) ((a) (b) ? (a) : (b))
17 using namespace std;
18 const int INF ~0u1;
19
20 int n;
21 int a[25][25];
22 struct tt{
23 int to, cost, next, cap;
24 }edge[5005];
25 int path[1005], top -1;
26 void Add(int u, int v, int cost, int cap);
27 int sta 999, fin 1000;
28 int min_cost_flow();
29 int SPFA();
30
31 int main(){
32 memset(path, -1, sizeof(path));
33 scanf(%d, n);
34 for (int i 0; i n; i)
35 for (int j 0; j n; j)
36 scanf(%d, a[i][j]);
37 for (int i 0; i n; i)
38 for (int j 0; j n; j){
39 Add(i*nj, (in)*nj, a[i][j], 1);
40 Add(i*nj, (in)*nj, 0, INF);
41 if (i ! n-1) Add((in)*nj, (i1)*nj, 0, INF);
42 if (j ! n-1) Add((in)*nj, i*nj1, 0, INF);
43 }
44 Add(sta, 0, 0, 3);
45 Add((2*n-1)*nn-1, fin, 0 ,3);
46 printf(%d\n, min_cost_flow());
47 return 0;
48 }
49
50 void Add(int u, int v, int cost, int cap){
51 edge[top].to v;
52 edge[top].cost cost;
53 edge[top].cap cap;
54 edge[top].next path[u];
55 path[u] top;
56 edge[top].to u;
57 edge[top].cost -cost;
58 edge[top].cap 0;
59 edge[top].next path[v];
60 path[v] top;
61 }
62 int min_cost_flow(){
63 int tolcost 0;
64 int tmp;
65 while (tmp SPFA()) tolcost tmp;
66 return tolcost;
67 }
68 int SPFA(){
69 int dist[1005];
70 memset(dist, 128, sizeof(dist)); dist[sta] 0; dist[fin] -INF;
71 bool vis[1005] {0}; vis[sta] 1;
72 queueintQ;
73 while (!Q.empty()) Q.pop();
74 Q.push(sta);
75 int pre[1005] {0};
76 while (!Q.empty()){
77 int u Q.front(); Q.pop(); vis[u]0;
78 for (int i path[u]; i ! -1; i edge[i].next){
79 int v edge[i].to;
80 if (dist[v] dist[u]edge[i].cost edge[i].cap 0){
81 dist[v] dist[u]edge[i].cost;
82 pre[v] i;
83 if (!vis[v]){
84 vis[v] 1;
85 Q.push(v);
86 }
87 }
88 }
89 }
90 if (dist[fin] -INF) return 0;
91 int minflow INF;
92 for (int i fin; i ! sta; i edge[pre[i]^1].to)
93 minflow Min(minflow, edge[pre[i]].cap);
94 for (int i fin; i ! sta; i edge[pre[i]^1].to)
95 edge[pre[i]].cap - minflow,
96 edge[pre[i]^1].cap minflow;
97 return dist[fin];
98 } 转载于:https://www.cnblogs.com/NaVi-Awson/p/7460488.html
