多重增广的核心在使用了一个记录回溯数组：在如下代码中为mark[]：
  Code
1 //hdu 3046
2
3#include "stdio.h"
4#include "string.h"
5#define N 40005
6#define M 1000000
7#define INF 1000000000
8
9int flow;
10int grid[205][205];
11int src,des;
12int R,L;
13struct Edge
14 {
15 int fr;
16 int w;
17 int to;
18 int nxt;
19 };
20Edge e[M];int en;
21int next[N];
22int mark[N];
23int lst[M];
24int h[N];
25bool vst[N];
26
27int n;
28int augc;
29
30void Insert(int fr,int to,int d,int dd)
31{
32 e[en].fr=fr;
33 e[en].w=d;
34 e[en].to=to;
35 e[en].nxt=next[fr];
36 next[fr]=en;
37 en++;
38 e[en].fr=to;
39 e[en].w=dd;
40 e[en].to=fr;
41 e[en].nxt=next[to];
42 next[to]=en;
43 en++;
44}
45bool bfs()
46{
47 int i,stt,end,x,y;
48 memset(h,-1,sizeof(h));
49 stt=0;
50 end=0;
51 lst[end++]=src;
52 h[src]=0;
53 while(stt<end)
54  {
55 x=lst[stt++];
56 for(i=next[x];i!=-1;i=e[i].nxt)
57 {
58 y=e[i].to;
59 if((e[i].w>0) && (h[y]==-1))
60 {
61 h[y]=h[x]+1;
62 lst[end++]=y;
63 }
64 }
65 }
66 return (h[des]>0);
67}
68
69int Min(int a,int b)
70{
71 if(a>b) return b;
72 else return a;
73}
74
75int dfs(int v,int augc)
76{
77 int i,x,t;
78 vst[v]=true;
79 if(v==des) return augc;
80 for(i=mark[v];i!=-1;i=e[i].nxt,mark[v]=i)//mark[]实现多重增广
81 {
82 x=e[i].to;
83 if((e[i].w>0)&&(h[x]==h[v]+1)&&(!vst[x]))
84 {
85 t=Min(augc,e[i].w);
86 if((t=dfs(x,t))>0)
87 {
88 e[i].w-=t;
89 e[i^1].w+=t;
90 return t;
91 }
92 }
93 }
94 return false;
95}
96
97void Dinic()
98{
99 int i;
100 flow=0;
101 while(bfs())
102 {
103 for(i=0;i<n;i++) mark[i]=next[i];
104 while(1)
105 {
106 memset(vst,false,sizeof(vst));
107 augc=dfs(src,INF);
108 if(!augc) break;
109 flow+=augc;
110 }
111 }
112 printf("%d\n",flow);
113}
114
115int main()
116{
117 int i,j,p,q;
118 int cn=1;
119 while(scanf("%d %d",&R,&L)!=EOF)
120 {
121 memset(next,-1,sizeof(next));
122 for(i=1;i<=R;i++)
123 {
124 for(j=1;j<=L;j++)
125 {
126 scanf("%d",&grid[i][j]);
127 }
128 }
129 src=0;
130 des=R*L+1;
131 en=0;
132 for(i=1;i<=R;i++)
133 {
134 for(j=1;j<=L;j++)
135 {
136 p=(i-1)*L+j;
137 q=p+L;
138 if(i<R)
139 Insert(p,q,1,1);
140 if(j<L)
141 Insert(p,p+1,1,1);
142 if(grid[i][j]==1)
143 Insert(src,p,INF,0);
144 if(grid[i][j]==2)
145 Insert(p,des,INF,0);
146 }
147 }
148 n=des+1;
149 printf("Case %d:\n",cn++);
150 Dinic();
151 }
152 return 0;
153}
154
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 31 | 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 | 1 | 2 | 3 | 4 | | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|
导航
统计
常用链接
留言簿
随笔分类(1)
随笔档案(2)
文章分类(15)
文章档案(7)
搜索
最新评论
阅读排行榜
评论排行榜
|
|