http://acm.hdu.edu.cn/showproblem.php?pid=3338
構圖我也不廢話了，有人說了怎么構
詳見http://www.cnblogs.com/ylfdrib/archive/2010/08/15/1799903.html
我只貼代碼，最好自己寫， 懂了構圖，完全可以看懂我的代碼。
1 //算法實現：ISAP算法（鄰接表實現）
2 #include <iostream>
3 #include <cstdio>
4 #include <cstring>
5 #define M 121
6 using namespace std;
7 const int maxn = 13201;
8 const int maxm = 200001;
9
10 struct Edge{
11
12 int flag;
13 int i, j;
14 }ee[maxn];
15
16 struct node {
17 //x起點，y終點,f容量,next是以x為起點的上一條邊在g中的位置,op是反向邊在g中的下標位置
18 int x, y, f, op, next;
19 }g[maxm * 2];
20
21 char mat[ M ][ M ][ 10 ];
22 char ans[ M ][ M ];
23 int a[ M ][ M ], va[ M ][ M ];
24 int c[ M ][ M ], vc[ M ][ M ];
25 int b[ M ][ M ];
26 int m, n, S, E, aid, ccc;
27
28 //first[]存儲的是以x為起點的最后一條邊的在數組g中的下標
29 //sumd[]用于記錄表示標號為i的頂點數有多少個，用于間隙優化
30 //now[]臨時記錄以x為起點的最后一條邊在數組g中的下標
31 int first[maxn],now[maxn],sumd[maxn];
32 int ncount; //代表結點的總數
33 int dis[maxn],fanhui[maxn],pre[maxn],tot; //dis[]用于記錄距離標號,pre[i]記錄i的前驅在g[]中的位置,tot記錄邊的總數
34
35 void insert(int x, int y, int c) {
36
37 tot++; //tot記錄邊的總數
38 g[tot].x=x;
39 g[tot].y=y;
40 g[tot].f=c;
41 g[tot].op=tot+1; //反向邊在g中的下標位置
42 g[tot].next=first[x]; //記錄以x為起點的上一條邊在g中的下標位置
43 first[x]=tot; //以x為起點的邊的位置
44 tot++;
45 //反向邊
46 g[tot].x=y;
47 g[tot].y=x;
48 g[tot].f=0; //反向邊的初始網絡流為0
49 g[tot].op=tot-1;
50 g[tot].next=first[y];
51 first[y]=tot;
52 }
53 //ISAP算法
54 int maxflow(int src, int des) {
55
56 int i,flow,t,j,tempmin; //i,j用于標識結點，t用于標識結點在g中的位置
57 bool flag; //用于標識是否找到了允許路徑
58 int sumFlow;
59 memset(dis,0,sizeof(dis)); //初始化dis為0
60 memset(sumd,0,sizeof(sumd));
61 for(i=1;i<=ncount;i++)
62 now[i]=first[i];
63 sumd[0]=ncount; //標號為0的結點有ncount個
64 sumFlow=0; //sumFlow記錄最大流，初始化為0
65 i=src; //i初始化為起點
66 flow=10000000;
67 while(dis[src]<ncount)
68 {
69 fanhui[i]=flow;
70 flag=false;
71 t=now[i];
72 while(t!=0) //尋找允許路徑
73 {
74 j=g[t].y;
75 if((g[t].f>0)&&(dis[j]+1==dis[i])) //允許弧
76 {
77 flag=true;
78 pre[j]=t;
79 now[i]=t;
80 if(g[t].f<flow) //找到允許增量
81 flow=g[t].f;
82 i=j;
83 if(i==ncount) //找到了允許路徑
84 {
85 sumFlow+=flow;
86 while(i!=src) //修改殘余網絡
87 {
88 g[pre[i]].f-=flow; //正向邊
89 g[g[pre[i]].op].f+=flow; //反向邊
90 i=g[pre[i]].x;
91 }
92 flow=10000000;
93 }
94 break;
95 }
96 t=g[t].next;
97 }
98 if(flag)
99 continue;
100 //沒有找到允許路徑
101 tempmin=ncount-1;
102 t=first[i];
103 while(t!=0)
104 {
105 if((g[t].f>0)&&(dis[g[t].y]<tempmin))
106 {
107 tempmin=dis[g[t].y];
108 now[i]=t;
109 }
110 t=g[t].next;
111 }
112 sumd[dis[i]]--;
113 if(sumd[dis[i]]==0) break; //間隙優化
114 dis[i]=tempmin+1; //此處別忘+1,因為d[i]=tempmin{d[j]+1|(i,j)在殘留網絡中}
115 sumd[dis[i]]++;
116 if(i!=src)
117 {
118 i=g[pre[i]].x;
119 flow=fanhui[i];
120 }
121 }
122 return sumFlow;
123 }
124
125 void solve(int i, int j) {
126
127 char str[10];
128 strcpy(str, mat[ i ][ j ]);
129
130 if(str[ 0 ] != 'X' && str[ 6 ] != 'X') {
131
132 int k;
133
134 c[ i ][ j ] = aid ++;
135 vc[ i ][ j ] = 0;
136 for(k = 0; k < 3; ++ k) {
137
138 if(str[ k ] >= '0' && str[ k ] <= '9') {
139
140 vc[ i ][ j ] = vc[ i ][ j ] * 10 + str[ k ] - '0';
141 }
142 }
143
144 a[ i ][ j ] = aid ++;
145 va[ i ][ j ] = 0;
146 for(k = 4;k < 7; ++ k) {
147
148 if(str[ k ] >= '0' && str[ k ] <= '9') {
149
150 va[ i ][ j ] = va[ i ][ j ] * 10 + str[ k ] - '0';
151 }
152 }
153 }
154 else if(str[ 0 ] != 'X') {
155
156 vc[ i ][ j ] = 0;
157 for(int k = 0; k < 3; ++ k) {
158
159 if(str[ k ] >= '0' && str[ k ] <= '9') {
160
161 vc[ i ][ j ] = vc[ i ][ j ] * 10 + str[ k ] - '0';
162 }
163 }
164 c[ i ][ j ] = aid ++;
165 }
166 else {
167
168 va[ i ][ j ] = 0;
169 a[ i ][ j ] = aid ++;
170
171 for(int k = 4;k < 7; ++ k) {
172
173 if(str[ k ] >= '0' && str[ k ] <= '9') {
174
175 va[ i ][ j ] = va[ i ][ j ] * 10 + str[ k ] - '0';
176 }
177 }
178 }
179 }
180
181
182 void print(int p[][101]) {
183
184 for(int i = 1; i <= m; ++ i) {
185
186 for(int j = 1; j <= n; ++ j)
187 printf("%3d", p[ i ][ j ]);
188 cout << endl;
189 }
190 cout << endl;
191 }
192
193 void init() {
194
195 aid = 1;
196 char str[10];
197 int i, j;
198
199 for(i = 1; i <= m; ++ i) {
200
201 for(j = 1; j <= n; ++ j) {
202
203 va[ i ][ j ] = -1; //va,vc先不要賦值0，否則像我一樣杯具30次
204 vc[ i ][ j ] = -1;
205 a[ i ][ j ] = -1;
206 b[ i ][ j ] = -1;
207 c[ i ][ j ] = -1;
208
209 strcpy(str, mat[ i ][ j ]);
210
211 if(str[ 0 ] != '.') {
212
213 ans[ i ][ j ] = '_';
214 if(str[ 0 ] != 'X' || str[ 6 ] != 'X')
215 solve(i, j);
216 }
217 else {
218
219 b[ i ][ j ] = aid ++;
220 }
221 }
222 }
223
224 //print(va);
225 //print(vc);
226
227 for(i = 1; i <= m; ++ i) {
228
229 for(j = 1; j <= n; ++ j) {
230
231 if(va[ i ][ j ] != -1) {
232
233 int csd = 0;
234 for(int k = j + 1; k <= n && mat[ i ][ k ][ 0 ] == '.'; ++ k) {
235
236 csd ++;
237 }
238 va[ i ][ j ] -= csd;
239 }
240
241 if(vc[ i ][ j ] != -1) {
242
243 int csd = 0;
244 for(int k = i + 1; k <= m && mat[ k ][ j ][ 0 ] == '.'; ++ k) {
245
246 csd ++;
247 }
248 vc[ i ][ j ] -= csd;
249 }
250 }
251 }
252
253 //print(va);
254 //print(vc);
255
256 for(i = 1; i <= m; ++ i) {
257
258 for(j = 1; j <= n; ++ j) {
259
260 if(i > 1) {
261
262 if(vc[ i ][ j ] == -1 && vc[i - 1][ j ] != -1) {
263
264 c[ i ][ j ] = c[i - 1][ j ];
265 vc[ i ][ j ] = vc[i - 1][ j ];
266 }
267 }
268
269 if(j > 1) {
270
271 if(va[ i ][ j ] == -1 && va[ i ][j - 1] != -1) {
272
273 a[ i ][ j ] = a[ i ][j - 1];
274 va[ i ][ j ] = va[ i ][j - 1];
275 }
276 }
277 }
278 //cout << endl;
279 }
280
281 ccc = 0;
282 tot = 0;
283 S = aid, E = aid + 1;
284 ncount = E;
285
286 memset(first, 0, sizeof(first));
287
288
289 //print(a);
290 //print(b);
291 //print(c);
292 //print(va);
293 //print(vc);
294
295 //cout << aid << endl;
296 }
297
298 void printRes() {
299
300 for(int i = 1; i <= m; ++ i) {
301
302 for(int j = 1; j < n; ++ j) {
303
304 printf("%c ", ans[ i ][ j ]);
305 }
306 printf("%c\n", ans[ i ][ j ]);
307 }
308 }
309
310
311 int main() {
312
313 int i, j;
314 while(scanf("%d %d", &m, &n) == 2) {
315
316 for(i = 1;i <= m; ++ i) {
317
318 for(j = 1; j <= n; ++ j) {
319
320 scanf("%s", mat[ i ][ j ]);
321 }
322 }
323
324 init();
325
326 bool aa[ maxn ];
327 for(i = 1; i <= ncount; ++ i)
328 aa[ i ] = false;
329
330
331 for(i = 1;i <= m; ++ i) {
332
333 for(j = 1; j <= n; ++ j) {
334
335 if(b[ i ][ j ] != -1) {
336
337 if(!aa[a[i][j]]) {
338
339 insert(S, a[i][j], va[i][j]);
340 aa[a[i][j]] = true;
341 }
342
343 insert(a[i][j], b[i][j], 8);
344
345 ee[ccc].flag = tot;
346 ee[ccc].i = i;
347 ee[ccc].j = j;
348 ccc ++;
349
350 insert(b[i][j], c[i][j], 8);
351
352 if(!aa[c[i][j]]) {
353
354 insert(c[i][j], E, vc[i][j]);
355 aa[c[i][j]] = true;
356 }
357 }
358 }
359 }
360
361 maxflow(S, E);
362
363 for(i = 0; i < ccc ; ++ i) {
364
365 int val = g[ee[ i ].flag].f;
366 int loci = ee[ i ].i;
367 int locj = ee[ i ].j;
368
369 ans[ loci ][ locj ] = val + '1';
370 }
371
372 printRes();
373 }
374 return 0;
375 }
376