misschuer

常用链接

统计

积分与排名

百事通

最新评论

hdu 3338 Kakuro Extension

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]]==0break;           //间隙优化
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, 0sizeof(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 


posted on 2010-10-20 18:54 此最相思 阅读(559) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理