学步园

拆点+最小割~

#include <cstdio>
  2 #include <cstring>
  3 
  4 constint MF = (1<<20);
  5 constint INF = (1<<30);
  6 
  7 class Network
  8 {
  9 private:
 10 conststaticint MAXV =512; // 顶点数
 11 conststaticint MAXE =512000; // 边数 * 2
 12 
 13 struct List
 14     {
 15 int v;
 16 int f;
 17         List * rev;
 18         List * next;
 19     };
 20 
 21     List pool[MAXE];
 22     List * path[MAXV];
 23     List * head[MAXV];
 24     List * cur[MAXV];
 25     List * pp;
 26 
 27 int n;
 28 int s;
 29 int t;
 30 int dist[MAXV];
 31 int num[MAXV];
 32 int pred[MAXV];
 33 
 34     inline List * create(int v,int f,List * next)
 35     {
 36         pp->v = v;
 37         pp->f = f;
 38         pp->next = next;
 39 return pp++;
 40     }
 41 
 42 void InitDist();
 43 void Augment(int&);
 44 public:
 45 void Init(int nv,int ss,int tt);
 46 void addEdge(int u,int v,int f);
 47 int maxFlow();
 48 };
 49 
 50 void Network::Init(int nv,int ss,int tt)
 51 {
 52     n = nv;
 53     s = ss;
 54     t = tt;
 55 
 56     pp = pool;
 57     memset(head,0,n *sizeof(head[0]));
 58     memset(cur,0,n *sizeof(cur[0]));
 59     memset(num,0,n *sizeof(int));
 60 
 61     pred[s] =-1;
 62 
 63 for (int i =0;i < n;i++)
 64         dist[i] = n;
 65 
 66 return;
 67 }
 68 
 69 void Network::addEdge(int u,int v,int f)
 70 {
 71     head[u] = create(v,f,head[u]);
 72     head[v] = create(u,0,head[v]);
 73 
 74     head[u]->rev = head[v];
 75     head[v]->rev = head[u];
 76 
 77 return;
 78 }
 79 
 80 void Network::InitDist()
 81 {
 82 int queue[MAXV];
 83 int qh =-1;
 84 int qe =0;
 85 
 86     dist[t] =0;
 87     queue[0] = t;
 88 
 89 while (qh != qe)
 90     {
 91         qh++;
 92 int u = queue[qh];
 93 for (List * p = head[u];p;p = p->next)
 94 if (p->f ==0&& dist[p->v] == n)
 95             {
 96                 dist[p->v] = dist[u] +1;
 97                 num[dist[p->v]]++;
 98                 queue[++qe] = p->v;
 99             }
100     }
101 
102 return;
103 }
104 
105 void Network::Augment(int& sum)
106 {
107 int minl = INF;
108 for (int u = t;u != s;u = pred[u])
109         minl = minl < path[u]->f ? minl : path[u]->f;
110     sum += minl;
111 for (int u = t;u != s;u = pred[u])
112     {
113         path[u]->f -= minl;
114         path[u]->rev->f += minl;
115     }
116 
117 return;
118 }
119 
120 int Network::maxFlow()
121 {
122 bool update;
123 int u = s;
124 int ret =0;
125 
126     InitDist();
127 for (int i =0;i < n;i++)
128         cur[i] = head[i];
129 
130 while (dist[s] < n)
131     {
132         update =false;
133 for (List * p = cur[u];p;p = p->next)
134 if (dist[p->v] +1== dist[u] && p->f >0)
135             {
136                 update =true;
137                 pred[p->v] = u;
138                 path[p->v] = p;
139                 cur[u] = p;
140                 u = p->v;    // 前进步
141 if (u == t)
142                 {
143                     Augment(ret);
144                     u = s;
145                 }
146 break;
147             }
148 if (!update)
149         {
150 if ( --num[dist[u]] ==0)    // 间隙优化
151 break;
152             cur[u] = head[u];
153             dist[u] = n;
154 for (List * p = head[u];p;p = p->next)    // 重标号
155 if (p->f >0&& dist[u] > dist[p->v] +1)
156                     dist[u] = dist[p->v] +1;
157 if (dist[u] < n)
158                 num[dist[u]]++;
159 if (u != s)                // 回退步
160                 u = pred[u];
161         }
162     }
163 return ret;
164 }
165 
166 Network net;
167 
168 int main()
169 {
170 int u;
171 int v;
172 int s;
173 int t;
174 int nv;
175 int nw;
176 int val;
177 int cas;
178 
179     scanf("%d",&cas);
180 
181 for(int cc =0;cc < cas;cc++)
182     {
183         scanf("%d %d %d %d",&nv,&nw,&s,&t);
184 
185         net.Init(2* nv,2* s -1,2* (t -1));
186 
187 for(int i =1;i <= nv;i++)
188         {
189             scanf("%d",&val);
190             net.addEdge(2* (i -1),2* i -1,val);
191         }
192 
193 for(int i =0;i < nw;i++)
194         {
195             scanf("%d %d",&u,&v);
196             net.addEdge(2* u -1,2* (v -1),MF);
197             net.addEdge(2* v -1,2* (u -1),MF);
198         }
199 
200         printf("%d\n",net.maxFlow());
201     }
202 
203 return0;
204 }