这道题以前做过了 今天有做了一遍，发现比以前顺手多了，
题意：
给一个N*N的方阵，从[1,1]到[n,n]走K次，走过每个方格加上上面的数（每一个 方格只能向下 后向右走）， 然后这个格上面的数变为0。求可取得的最大的值。
题解：
拆点 + 费用流 ；
将 每一个点拆分成两个 ， 为了 保证 只能算一次 流量为1 花费为 方格的值，有为了 保证 其他的路径 可以 从这个点 走过 再建一条 流量 为 inf 费用 为 0 的 边
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 10001000
16 #define mx 1<<60
17 #define ll __int64
18
19 #define read() freopen("data.txt","r",stdin) ;
20 const double pi = acos(-1.0);
21 const int maxn = 100000;
22
23 using namespace std;
24 int n , m , k ,s,ss,t,N;
25 int mat[60][60] ,dis[6000],head[6000],cnt,pre[6000];
26 bool vis[6000] ;
27 struct node
28 {
29 int v;
30 int cost;
31 int flow;
32 int next ;
33 }p[maxn] ;
34 struct qnode
35 {
36 int u;
37 int len ;
38 qnode(int a,int b):u(a),len(b){}
39
40 };
41 queue<qnode>que ;
42
43
44 void add(int u,int v,int f,int c)
45 {
46 p[cnt].v = v;
47 p[cnt].cost = c ;
48 p[cnt].flow = f;
49 p[cnt].next = head[u];
50 head[u] = cnt++;
51
52
53
54 p[cnt].v = u;
55 p[cnt].cost = -c;
56 p[cnt].flow = 0;
57 p[cnt].next = head[v] ;
58 head[v] = cnt++ ;
59
60 }
61 void build()
62 {
63 int i , j ,b;
64 CL(head,-1);
65
66 cnt = 0 ;
67 N = n*n ;
68 s = n*n *2+ 1 ;
69 t = n*n *2 + 2 ;
70 add(s,0,k,0);
71
72 for(i = 0 ; i < n;i++)
73 {
74 for(j = 0 ; j< n;j++)
75 {
76 int a = i*n + j;
77
78 add(a,a + N,1,mat[i][j]) ;
79 add(a,a+N,inf,0) ;
80 if(i + 1 < n)
81 {
82 b = (i + 1)*n + j ;
83 add(a + N,b,inf,0) ;
84 }
85
86 if(j + 1 < n)
87 {
88 b = i * n + (j + 1) ;
89 add(a + N,b,inf,0) ;
90 }
91
92 if(i == n - 1&&j == n - 1)
93 {
94 add(a + N,t,inf,0);
95 }
96 }
97 }
98
99
100
101 }
102 bool spfa(int s)
103 {
104
105 int i ;
106 for(i = 0 ; i <= t;i++)
107 {
108 dis[i] = -inf;
109 }
110 dis[s] = 0 ;
111 CL(vis,false) ;
112 while(!que.empty())que.pop() ;
113
114 que.push(qnode(s,0));
115 vis[s] =true ;
116 while(!que.empty())
117 {
118 qnode a = que.front() ;que.pop() ;
119
120 int u = a.u;
121 int len = a.len ;
122 vis[u] = false ;
123 for(i = head[u];i != - 1;i = p[i].next)
124 {
125 int v = p[i].v;
126 int cost = p[i].cost;
127 int flow = p[i].flow ;
128 if(flow > 0 && dis[v] < dis[u] + cost)
129 {
130
131 dis[v] = dis[u] + cost;
132 pre[v] = i;
133 if(!vis[v])
134 {
135 vis[v] = true ;
136 que.push(qnode(v,dis[v])) ;
137 }
138 }
139 }
140 }
141 return dis[t] > 0 ;
142
143 }
144 void solve()
145 {
146 int i, j;
147 int res = -inf ;
148
149
150
151 int ans = 0 ;
152
153 while(spfa(s))
154 {
155
156
157 int mi = inf;
158 int tp = t;
159 /*while(tp!= s)
160 {
161
162
163 mi = min(mi,p[pre[tp]].flow) ;
164 tp = p[pre[tp]^1].v ;// 跳到 出边点
165 }
166 tp = t;*/
167 while(tp!= s)
168 {
169
170 ans += p[pre[tp]].cost ;
171 p[pre[tp]].flow -= 1 ;
172 p[pre[tp]^1].flow += 1;
173
174 tp = p[pre[tp]^1].v;
175
176 }
177 }
178
179
180
181 printf("%d\n",ans) ;
182
183 }
184 int main()
185 {
186 int i ,u,v,d,j;
187 //read();
188 while(scanf("%d%d",&n,&k)!=EOF)
189 {
190 for(i = 0 ; i< n;i++)
191 {
192 for(j = 0 ; j < n;j++)
193 {
194 scanf("%d",&mat[i][j]) ;
195 }
196 }
197 build() ;
198 solve() ;
199 }
200 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define eps 1e-12
15 #define inf 10001000
16 #define mx 1<<60
17 #define ll __int64
18
19 #define read() freopen("data.txt","r",stdin) ;
20 const double pi = acos(-1.0);
21 const int maxn = 100000;
22
23 using namespace std;
24 int n , m , k ,s,ss,t,N;
25 int mat[60][60] ,dis[6000],head[6000],cnt,pre[6000];
26 bool vis[6000] ;
27 struct node
28 {
29 int v;
30 int cost;
31 int flow;
32 int next ;
33 }p[maxn] ;
34 struct qnode
35 {
36 int u;
37 int len ;
38 qnode(int a,int b):u(a),len(b){}
39
40 };
41 queue<qnode>que ;
42
43
44 void add(int u,int v,int f,int c)
45 {
46 p[cnt].v = v;
47 p[cnt].cost = c ;
48 p[cnt].flow = f;
49 p[cnt].next = head[u];
50 head[u] = cnt++;
51
52
53
54 p[cnt].v = u;
55 p[cnt].cost = -c;
56 p[cnt].flow = 0;
57 p[cnt].next = head[v] ;
58 head[v] = cnt++ ;
59
60 }
61 void build()
62 {
63 int i , j ,b;
64 CL(head,-1);
65
66 cnt = 0 ;
67 N = n*n ;
68 s = n*n *2+ 1 ;
69 t = n*n *2 + 2 ;
70 add(s,0,k,0);
71
72 for(i = 0 ; i < n;i++)
73 {
74 for(j = 0 ; j< n;j++)
75 {
76 int a = i*n + j;
77
78 add(a,a + N,1,mat[i][j]) ;
79 add(a,a+N,inf,0) ;
80 if(i + 1 < n)
81 {
82 b = (i + 1)*n + j ;
83 add(a + N,b,inf,0) ;
84 }
85
86 if(j + 1 < n)
87 {
88 b = i * n + (j + 1) ;
89 add(a + N,b,inf,0) ;
90 }
91
92 if(i == n - 1&&j == n - 1)
93 {
94 add(a + N,t,inf,0);
95 }
96 }
97 }
98
99
100
101 }
102 bool spfa(int s)
103 {
104
105 int i ;
106 for(i = 0 ; i <= t;i++)
107 {
108 dis[i] = -inf;
109 }
110 dis[s] = 0 ;
111 CL(vis,false) ;
112 while(!que.empty())que.pop() ;
113
114 que.push(qnode(s,0));
115 vis[s] =true ;
116 while(!que.empty())
117 {
118 qnode a = que.front() ;que.pop() ;
119
120 int u = a.u;
121 int len = a.len ;
122 vis[u] = false ;
123 for(i = head[u];i != - 1;i = p[i].next)
124 {
125 int v = p[i].v;
126 int cost = p[i].cost;
127 int flow = p[i].flow ;
128 if(flow > 0 && dis[v] < dis[u] + cost)
129 {
130
131 dis[v] = dis[u] + cost;
132 pre[v] = i;
133 if(!vis[v])
134 {
135 vis[v] = true ;
136 que.push(qnode(v,dis[v])) ;
137 }
138 }
139 }
140 }
141 return dis[t] > 0 ;
142
143 }
144 void solve()
145 {
146 int i, j;
147 int res = -inf ;
148
149
150
151 int ans = 0 ;
152
153 while(spfa(s))
154 {
155
156
157 int mi = inf;
158 int tp = t;
159 /*while(tp!= s)
160 {
161
162
163 mi = min(mi,p[pre[tp]].flow) ;
164 tp = p[pre[tp]^1].v ;// 跳到 出边点
165 }
166 tp = t;*/
167 while(tp!= s)
168 {
169
170 ans += p[pre[tp]].cost ;
171 p[pre[tp]].flow -= 1 ;
172 p[pre[tp]^1].flow += 1;
173
174 tp = p[pre[tp]^1].v;
175
176 }
177 }
178
179
180
181 printf("%d\n",ans) ;
182
183 }
184 int main()
185 {
186 int i ,u,v,d,j;
187 //read();
188 while(scanf("%d%d",&n,&k)!=EOF)
189 {
190 for(i = 0 ; i< n;i++)
191 {
192 for(j = 0 ; j < n;j++)
193 {
194 scanf("%d",&mat[i][j]) ;
195 }
196 }
197 build() ;
198 solve() ;
199 }
200 }