1 图算法
  2 kurXX最小生成树
  3 #include <iostream>
  4 #include <math.h>
  5 #include <algorithm>
  6 using namespace std;
  7 #define M 501
  8 #define LIM 20000000
  9 
 10 struct edg{
 11     int u,v;
 12     int w;
 13 }all_e[M*M/2];
 14 bool operator < (const edg &a,const edg &b){
 15     return a.w<b.w;
 16 }
 17 int set[M];
 18 
 19 inline bool uni(int set[],int a,int b){ 
 20     int ac=0,a2=a,b2=b,bc=0;
 21     while(set[a]!=0) {a=set[a];ac++;}
 22     if(a2!=a) set[a2]=a;
 23     while(set[b]!=0) {b=set[b];bc++;}
 24     if(b2!=b) set[b2]=b;  
 25     if(a==b) return false;
 26     if(ac<bc) set[a]=b;
 27     else set[b]=a;
 28     return true;
 29 }
 30 int main(){
 31     int i,j,k,n,m,u,v,t;
 32     cin >> t;
 33     for(k=0;k<t;k++){
 34     memset(set,0,sizeof(set));
 35     cin >> n;
 36     int ei=0;
 37     for(i=1;i<=n;i++){
 38         for(j=1;j<=n;j++){
 39             if(t!=0){
 40                 edg e;
 41                 e.u=i;e.v=j;
 42                 scanf("%d",&e.w);
 43                 if(i<j)
 44                     all_e[ei++]=e;
 45             }
 46         }
 47     }
 48     sort(&all_e[0],&all_e[ei]);
 49     int count=0;
 50     int size=ei;
 51     int max=0;
 52     for(i=0;i<size && count < n-1;i++){
 53         if(uni(set,all_e[i].u,all_e[i].v)){
 54             count++;
 55             if(all_e[i].w>all_e[max].w) max=i;
 56         }
 57     }
 58     printf("%d\n",all_e[max].w);
 59     }
 60     return 0;
 61 }
 62 Prim
 63 #include <iostream>
 64 using namespace std;
 65 #define M 2001
 66 
 67 int set[M]={0},g[M][M];
 68 char str[M][8];
 69 
 70 inline void make_map(int n,int g[M][M]){
 71     int i,j,k;
 72     for(i=1;i<=n;i++){
 73         for(j=i+1;j<=n;j++){
 74             int c=0;
 75             for(k=0;k<7;k++)
 76                 if(str[i][k]!=str[j][k]) c++;
 77             g[i][j]=g[j][i]=c;
 78         }
 79     }
 80 }
 81 
 82 int main(){
 83     int n,q[M],qf=0,ql=0,d[M],u;
 84     char c;
 85     scanf("%d%c",&n,&c);
 86     int i;
 87     while(n!=0){
 88         memset(set,0,sizeof(set)); memset(g,0,sizeof(g));
 89         for(i=1;i<=n;i++) {
 90             scanf("%s",&str[i]);
 91             q[i-1]=i;
 92             d[i]=2000000;
 93         }
 94         qf=0;ql=n-1;
 95         make_map(n,g);
 96         int sum=0;
 97         int f=false;
 98         while(qf<=ql){
 99             int min=qf;
100             for(i=qf+1;i<=ql;i++){
101                 if(d[q[i]] < d[q[min]]) min=i;
102             }
103             swap(q[qf],q[min]);
104             u=q[qf]; qf++;
105             if(f) sum+=d[u];
106             for(i=1;i<=n;i++){
107                 if(g[u][i] !=0 && g[u][i] < d[i]) d[i]=g[u][i];
108             }
109             f=true;
110         }
111         printf("The highest possible quality is 1/%d.\n",sum);
112         scanf("%d%c",&n,&c);
113     }
114     return 0;
115 }
116 堆实现最短路
117 #include <iostream>
118 #include <string>
119 #include <stdlib.h>
120 #include <vector>;
121 using namespace std;
122 #define M 1001
123 #define LIM 2000000000
124 
125 struct dd{ //最短距离
126     int w,q;//w是距离值,q是堆中的相对位置
127 }d[M],d2[M];
128 struct node{
129     int v,w;
130 };
131 int h[M],hs;
132 vector<node> g[M],g2[M];
133 void change_key(dd d[M],int v,int w){
134     d[v].w=w;
135     int i=d[v].q;
136     while(i>1 && d[h[i/2]].w>d[h[i]].w){
137         swap(h[i],h[i/2]);
138         swap(d[h[i]].q,d[h[i/2]].q);
139         i=i/2;
140     }
141 }
142 inline void min_heaphy(dd d[M],int *a,int i,int s){//s 为堆大小
143     int l=i*2,r=i*2+1;
144     int miner=i;
145     if (l<=s && d[a[i]].w>d[a[l]].w)
146         miner = l;
147     else miner=i;
148     if (r<=s && d[a[miner]].w>d[a[r]].w)
149         miner=r;
150     if(miner!=i){
151         swap(a[i],a[miner]);
152         swap(d[a[i]].q,d[a[miner]].q);
153         min_heaphy(d,a,miner,s);
154     }
155 }
156 inline void init(dd d[M],int n,int s){  //初始化图和堆
157     int i;
158     hs=n;
159     for(i=1;i<=n;i++){d[i].w=LIM;h[i]=d[i].q=i;}
160     change_key(d,s,0);
161 }
162 inline void relax(dd d[M],int u,int v,int duv){
163     if(d[v].w>d[u].w+duv) change_key(d,v,d[u].w+duv);
164 }
165 void dijkstra(vector<node> g[M],dd d[M],int n,int s){ //n is |V| && s is the source
166     init(d,n,s);
167     int i;
168     while(hs!=0){
169         int u=h[1];
170         swap(h[1],h[hs]);
171         swap(d[h[1]].q,d[h[hs]].q);
172         hs--;
173         min_heaphy(d,h,1,hs);
174         for(i=0;i<g[u].size();i++) relax(d,u,g[u][i].v,g[u][i].w);
175     }
176 }
177 最短路DIJ普通版
178 #define M 101
179 #define LIM 20000000
180 
181 int g[M][M],d[M],fd[2][M][M],gt[M][M],set[M];
182 inline void init(int d[M],int n,int s){  //初始化图
183     int i;
184     for(i=1;i<=n;i++)    d[i]=LIM;
185     d[s]=0;
186 }
187 
188 inline void relax(int d[M],int u,int v,int duv){
189     if(d[v]>d[u]+duv)    d[v]=d[u]+duv;
190 }
191 void dijkstra(int g[M][M],int d[M],int n,int s){ //n is |V| && s is the source
192     init(d,n,s);
193     int q[M],ql=1,qf=1; //队列
194     int i;
195     for(i=1;i<=n;i++) q[ql++]=i;
196     while(qf!=ql){
197         int min=qf;
198         for(i=qf;i<ql;i++) if(d[q[i]]<d[q[min]]) min=i; 
199         swap(q[qf],q[min]); //q[qf] is the min
200         int u=q[qf++];
201         for(i=1;i<=n;i++){
202             if(g[u][i]!=0) relax(d,u,i,g[u][i]);
203         }
204     }
205 }
206 floyd
207 #include <iostream>
208 #include <vector>
209 using namespace std;
210 #define M 301
211 #define LIM 200000000
212 int w[M][M],d[2][M][M];
213 
214 void floyd(int g[M][M],int d[2][M][M],int n){
215     int i,j,k;
216     for(i=1;i<=n;i++){
217         for(j=1;j<=n;j++){
218             d[0][i][j]=g[i][j];
219         }
220         d[0][i][i]=0;
221     }        //这里是令d[0]=g
222     for(k=1;k<=n;k++){
223         for(i=1;i<=n;i++)
224             for(j=1;j<=n;j++){
225                 int t1=k%2; int t2=(t1+1)%2;
226                 d[t1][i][j]=d[t2][i][j] < d[t2][i][k]+d[t2][k][j]?d[t2][i][j]:d[t2][i][k]+d[t2][k][j];
227             }
228     }
229 }
230 BELL_MAN
231 inline void init(int d[M],int n,int s){  //初始化图
232     int i;
233     for(i=1;i<=n;i++)    d[i]=2000000000;
234     d[s]=0;
235 }
236 
237 inline void relax(int d[M],int u,int v,int duv){
238     if(d[v]>d[u]+duv)    d[v]=d[u]+duv;
239 }
240 
241 void bell_man(int g[M][M],int d[M],int n,int s){ //n个结点 s为源点
242     int i,j,k;
243     init(d,n,s);
244     for(k=1;k<n;k++){
245         for(i=1;i<=n;i++)
246             for(j=1;j<=n;j++){
247                 if(g[i][j]!=0) relax(d,i,j,g[i][j]);
248             }
249     }
250 }
251 拓扑排序
252 #include <iostream>
253 #include <stack>
254 #include <vector>
255 #include <list>
256 using namespace std;
257 vector <int> order;
258 void find_id(list<int> g[],int id[],int n){  //寻找入度,没有使用
259     int i;
260     list<int>::iterator k;
261     for(i=0;i<n;i++){
262         for(k=g[i].begin();k!=g[i].end();k++){
263             id[*k]++;
264         }
265     }
266 }
267 void topo(list<int> g[],int id[],int n,bool &OK,bool &incon){//OK==false 表示未确定顺序 incon==true 表示发现矛盾
268     stack<int> s;
269     order.erase(order.begin(),order.end());
270     int t[26];
271     copy(&id[0],&id[n],&t[0]);
272     int i;
273     for(i=0;i<n;i++){
274         if(id[i]==0) 
275             s.push(i);
276     }
277     if(s.size()!=1) OK=false;
278     int count=0;
279     while(!s.empty()){
280         int v=s.top(); s.pop(); count++;
281         order.push_back(v);
282         list<int>::iterator k;
283         for(k=g[v].begin();k!=g[v].end();k++){
284             id[*k]--;
285             if(id[*k]==0) s.push(*k);
286             if(s.size()>1) OK=false;
287         }
288     }
289     if(order.size() < n) OK=false;   //矛盾发生,会导致这种情况,小心
290     if(count < n) incon=true;
291     copy(&t[0],&t[n],&id[0]);
292 }
293 DFS强连通分支
294 #include <iostream>
295 #include <algorithm>
296 #include <vector>
297 using namespace std;
298 #define M 20005
299 vector<int> g[M],gt[M];
300 bool used[M];
301 int ft[M],sort_v[M],tim;
302 bool comp(const int &u,const int &v){
303     return ft[u]>ft[v];
304 }
305 inline int findp(int set[],int n){
306     int n2=n;
307     while(set[n]!=0) n=set[n];
308     if(n2!=n) set[n2]=n;
309     return n;
310 }
311 inline bool uni(int set[],int a,int b){ 
312     int ac=0,a2=a,b2=b,bc=0,t;
313     while(set[a]!=0) {a=set[a];ac++;}
314     while(a2!=a) {t=set[a2]; set[a2]=a; a2=t;};
315     while(set[b]!=0) {b=set[b];bc++;}
316     while(b2!=b) {t=set[b2]; set[b2]=b; b2=t;}; 
317     if(a==b) return false;
318     if(ac<bc) set[a]=b;
319     else set[b]=a;
320     return true;
321 }
322 void dfs(vector<int> g[M],int u){
323     if(used[u]) return;
324     tim++;
325     used[u]=true;
326     int i;
327     for(i=0;i<g[u].size();i++){
328         dfs(g,g[u][i]);
329     }
330     tim++;
331     ft[u]=tim;
332     return;
333 }
334 void dfs2(vector<int> g[],int u,int r,int set[]){
335     if(used[u]) return;
336     uni(set,u,r);
337     used[u]=true;
338     int i;
339     for(i=0;i<g[u].size();i++){
340         dfs2(g,g[u][i],u,set);
341     }
342     return;
343 }
344 void scc(int n,vector<int> g[M],int set[]){
345     int i,j;
346     tim=0;
347     memset(used,0,sizeof(used));
348     memset(set,0,sizeof(set));
349     for(i=1;i<=n;i++) sort_v[i]=i;
350     for(i=1;i<=n;i++) if(!used[i]) dfs(g,i); //compute finishing times
351     sort(&sort_v[1],&sort_v[n+1],comp); //decreasing f[u] order
352     memset(used,0,sizeof(used));  
353     for(i=1;i<=n;i++) for(j=0;j<g[i].size();j++) gt[g[i][j]].push_back(i); //compute gt
354     for(i=1;i<=n;i++) if(!used[sort_v[i]]) dfs2(gt,sort_v[i],sort_v[i],set);  //make the scc
355 }
356 int main(){
357     int i,j,n,m,u,v,set[M];
358     cin >> n >> m;
359     for(i=0;i<m;i++){
360         scanf("%d%d",&u,&v);
361         g[u].push_back(v);
362     }
363     scc(n,g,set);
364     int pi=1,ptosc[M];
365     struct Scc{
366         int p,n;
367     }sc[M];
368     memset(sc,0,sizeof(sc));
369     for(i=1;i<=n;i++){
370         int p=findp(set,i);
371         if(sc[p].p==0) {sc[p].p=pi; ptosc[pi++]=p;}
372         sc[p].n++;
373     }
374     int n2=pi-1,od[M];
375     memset(od,0,sizeof(od));
376     for(i=1;i<=n;i++){
377         for(j=0;j<g[i].size();j++){
378             u=findp(set,i); v=findp(set,g[i][j]);
379             if(sc[u].p!=sc[v].p) od[sc[u].p]++;
380         }
381     }
382     int sum=0,s1=0;
383     for(i=1;i<=n2;i++) if(od[i]==0) {s1++; sum+=sc[ptosc[i]].n;}
384     if(s1!=1) sum=0;
385     cout << sum << endl;
386 }
387 最大匹配
388 #include <iostream>
389 #include <string>
390 #include <math.h>
391 using namespace std;
392 #define M 1001
393 
394 int n,m,match[M],ans[M];
395 bool visit[M],g[M][M];
396 //O(n^3)
397 bool dfs(int k,bool map[M][M]){  
398     int t;
399     for(int i = 1; i <= m; i++){
400         if(map[k][i] && !visit[i]){
401             visit[i] = true;
402             t = match[i];
403             match[i] = k;
404             if(t == 0 || dfs(t,map))
405                 return true;
406             match[i] = t;
407         }
408     }
409     return false;
410 }
411 int main(){
412     int i,sum=0,t,j,u,v;
413     cin >> t;
414     while(t--){
415         sum=0;
416         memset(match,0,sizeof(match));
417         memset(g,0,sizeof(g));
418         scanf("%d%d",&n,&m);
419         for(i=1;i<=m;i++){
420             scanf("%d%d",&u,&v);
421             g[u][v]=true;
422         }
423         m=n;
424         for(i=1;i<=n; i++){
425             memset(visit,0,sizeof(visit));
426             if(dfs(i,g))  sum++;
427         }
428         cout << n-sum << endl;
429     }
430     return 0;
431 }
432 还有两个最大匹配模板
433 #include <iostream>
434 #include <string>
435 #include <math.h>
436 #include <vector>
437 using namespace std;
438 #define M 3001
439 
440 bool g[M][M];
441 int mk[M] ,cx[M],pred[M],open[M],cy[M],nx,ny;
442 
443 
444 //边少适用O(n^3)
445 int MaxMatchBFS()
446 {
447     int i , u , v , t , d , e , cur , tail , res(0) ;
448     memset(mk , 0xff , sizeof(mk)) ; 
449     memset(cx , 0xff , sizeof(cx)) ;
450     memset(cy , 0xff , sizeof(cy)) ;
451     for (i = 0 ; i < nx ; i++){
452         pred[i] = -1 ;
453         for (open[cur = tail = 0] = i ; cur <= tail && cx[i] == -1 ; cur++){
454             for (u = open[cur] , v = 0 ; v < ny && cx[i] == -1 ; v ++) if (g[u][v] && mk[v] != i)
455             {
456                 mk[v] = i ; open[++tail] = cy[v] ; if (open[tail] >= 0) { pred[open[tail]] = u ; continue ; }
457                 for (d = u , e = v ; d != -1 ; t = cx[d] , cx[d] = e , cy[e] = d , e = t , d = pred[d]) ;
458             }
459         }
460         if (cx[i] != -1) res++ ;
461     }
462     return res ;
463 }
464 
465 int path(int u){
466     for (int v = 0 ; v < ny ; v++) 
467         if (g[u][v] && !mk[v]){
468             mk[v] = 1 ; 
469             if (cy[v] == -1 || path(cy[v])) {
470                 cx[u] = v ; 
471                 cy[v] = u ; 
472                 return 1 ; 
473             }
474         } return 0 ;
475 }
476 //少适用O(n^3)
477 int MaxMatchDFS()
478 {
479     int res(0) ;
480     memset(cx , 0xff , sizeof(cx)) ; 
481     memset(cy , 0xff , sizeof(cy)) ;
482     for (int i = 0 ; i < nx ; i++) 
483         if (cx[i] == -1){
484             memset(mk , 0 , sizeof(mk)); 
485             res += path(i) ;
486         }
487         return res ;
488 }
489 最大权匹配,KM算法
490 //此KM算法，坐标从1开始，记住
491 #include <iostream>
492 #include <vector>
493 #include <math.h>
494 using namespace std;
495 #define M 110
496 
497 int n;                // X 的大小
498 int lx[M], ly[M];        // 标号
499 bool sx[M], sy[M];    // 是否被搜索过
500 int match[M];        // Y(i) 与 X(match [i]) 匹配
501 
502 // 从 X(u) 寻找增广道路，找到则返回 true
503 bool path(int u,int weight[M][M]) {
504     sx [u] = true;
505     for (int v = 0; v < n; v ++)
506         if (!sy [v] && lx[u] + ly [v] == weight [u] [v]) {
507             sy [v] = true;
508             if (match [v] == -1 || path(match [v],weight)) {
509                 match [v] = u;
510                 return true;
511             }
512         }
513     return false;
514 }
515 // 参数 Msum 为 true ，返回最大权匹配，否则最小权匹配
516 int km(bool Msum,int weight[M][M]) {
517     int i, j;
518     if (!Msum) {
519         for (i = 0; i < n; i ++)
520             for (j = 0; j < n; j ++)
521                 weight [i] [j] = -weight [i] [j];
522     }
523     // 初始化标号
524     for (i = 0; i < n; i ++) {
525         lx [i] = -0x1FFFFFFF;
526         ly [i] = 0;
527         for (j = 0; j < n; j ++)
528             if (lx [i] < weight [i] [j])
529                 lx [i] = weight [i] [j];
530     }  
531     memset(match, -1, sizeof (match));
532     for (int u = 0; u < n; u ++)
533         while (1) {
534             memset(sx, 0, sizeof (sx));
535             memset(sy, 0, sizeof (sy));
536             if (path(u,weight))
537                 break;      
538             // 修改标号
539             int dx = 0x7FFFFFFF;
540             for (i = 0; i < n; i ++)
541                 if (sx [i])
542                     for (j = 0; j < n; j ++)
543                         if(!sy [j])
544                             dx = min(lx[i] + ly [j] - weight [i] [j], dx);
545             for (i = 0; i < n; i ++) {
546                 if (sx [i])
547                     lx [i] -= dx;
548                 if (sy [i])
549                     ly [i] += dx;
550             }
551         }
552     
553     int sum = 0;
554     for (i = 0; i < n; i ++)
555         sum += weight [match [i]] [i];
556     
557     if (!Msum) {
558         sum = -sum;
559         for (i = 0; i < n; i ++)
560             for (j = 0; j < n; j ++)
561                 weight [i] [j] = -weight [i] [j];         // 如果需要保持 weight [ ] [ ] 原来的值，这里需要将其还原
562     }
563     return sum;
564 }
565 
566 struct Point{
567     int r,c;
568 };
569 int main(){
570     int i,j,m;
571     freopen("in","r",stdin);
572     int w[M][M];
573     char c; Point pt;
574     while(cin >> n >> m && (n!=0 || m!=0)){
575         vector<Point> vh,vm;
576         for(i=0;i<n;i++){
577             getchar();
578             for(j=0;j<m;j++){
579                 scanf("%c",&c);
580                 if(c=='H'){
581                     pt.r=i; pt.c=j;
582                     vh.push_back(pt);
583                 }
584                 if(c=='m'){
585                     pt.r=i;pt.c=j;
586                     vm.push_back(pt);
587                 }
588             }
589         }
590         for(i=0;i<vm.size();i++) for(j=0;j<vh.size();j++) w[i][j]=abs(vm[i].r-vh[j].r)+abs(vm[i].c-vh[j].c);
591         n=vm.size();
592         cout << km(false,w)<< endl;
593     }
594 }
595 两种欧拉路
596 无向图：
597 #define M 45
598 int used[M][M],id[M];
599 void dfs(int u,vector<int> g[],vector<int> &vans){  //O（E^2）
600     int j,w,v,t;
601     for(j=g[u].size()-1;j>=0;j--){
602         t=v=g[u][j]; w=u;
603         if(v>w) swap(v,w);
604         if(used[v][w]!=0){
605             used[v][w]--;
606             dfs(t,g,vans);
607         }
608     }
609     vans.push_back(u);
610 }
611 
612 有向图：
613 int n,m;
614 vector<int> g[M],vans;
615 void dfs(int u){   //O（E^2*log(e)）
616     int j,t;
617     Edg et;
618     for(j=g[u].size()-1;j>=0;j--){
619         et.u=u; et.v=g[u][j];
620         if(mp[et]!=0){
621             mp[et]--;
622             dfs(g[u][j]);
623         }
624     }
625     vans.push_back(u);
626 }
627 
628 【最大流】Edmonds Karp
629 //求最小割集合的办法:
630 //设置一个集合A, 最开始A={s},按如下方法不断扩张A:
631 //1 若存在一条边(u,v), 其流量小于容量，且u属于A,则v加入A
632 //2 若存在(v,u), 其流量大于0，且u属于A,则v加入A
633 
634 //A计算完毕，设B=V-A，
635 //最大流对应的割集E={(u,v) | u∈A,v∈B}
636 //E为割集，这是一定的
637 
638 //【最大流】Edmonds Karp算法求最大流,复杂度 O(V E^2)。返回最大流,输入图容量
639 //矩阵g[M][M],取非零值表示有边，s为源点，t为汇点，f[M][M]返回流量矩阵。
640 
641 int f[M][M],g[M][M];
642 
643 int EdmondsKarp(int n,int s,int t){    
644     int i,j,k,c,head,tail,flow=0;
645     int r[M][M];
646     int prev[M],visit[M],q[M];
647     for (i=1;i<=n;i++) for (j=1;j<=n;j++) {f[i][j]=0;r[i][j]=g[i][j];} //初始化流量网络和残留网络
648     while (1) { //在残留网络中找到一条s到t的最短路径
649         head=tail=0;
650         memset(visit,0,sizeof(visit));
651         q[tail++]=s;
652         prev[s]=-1; visit[s]=1;
653         while(head!=tail){  //宽度优先搜索从s到t的最短路径
654             k=q[head++];
655             for (i=1;i<=n;i++)
656                 if (!visit[i] && r[k][i]>0) {
657                     visit[i]=1;
658                     prev[i]=k;
659                     if (i==t) goto next;
660                     q[tail++]=i;
661                 }
662         }
663 next:    
664         if (!visit[t]) break; //流量已达到最大
665         c=99999999;
666         j=t;
667         while (j!=s) {
668             i=prev[j];
669             if (c>r[i][j]) c=r[i][j];
670             j=i;
671         }
672         //下面改进流量
673         j=t;
674         while (j!=s) {
675             i=prev[j];
676             f[i][j]+=c;
677             f[j][i]=-f[i][j];
678             r[i][j]=g[i][j]-f[i][j];
679             r[j][i]=g[j][i]-f[j][i];
680             j=i;
681         }
682         flow+=c;
683         //cout << c << endl;
684     }
685     return flow;
686 }
687 dinic
688 /* 
689 dinic 
690 BFS+多路增广 
691 这个模板是OIBH上的Code_Rush的，他写的Dinic和别人的不太一样，速度更快 
692 O(mn^2) 
693 */ 
694 
695 #include<stdio.h> 
696 #include<list> 
697 #include<queue> 
698 #include<string.h> 
699 #include <vector>
700 #include <iostream>
701 using namespace std; 
702 #define M 201
703 int pre[M]; 
704 int f[M][M],g[M][M]; 
705 bool b[M]={0}; 
706 
707 //g为输入的图容量矩阵,f为返回流量矩阵
708 int dinic(int n,int s,int t) 
709 { 
710     memset(f,0,sizeof(f));
711     int ans=0; 
712     while(true) 
713     {
714         queue<int> q; 
715         fill(pre,pre+n+2,-1); 
716         fill(b,b+n+2,0); 
717         q.push(s);b[s]=1; 
718         while(!q.empty()) 
719         { 
720             int x=q.front();q.pop(); 
721             if(x==t)break; 
722             for(int i=1;i<=n;i++) 
723             {
724                 if(!b[i]&&f[x][i]<g[x][i]) 
725                 { 
726                     pre[i]=x; 
727                     b[i]=1; 
728                     q.push(i); 
729                 } 
730             }
731         } 
732         if(pre[t]==-1)break; 
733         for(int i=1;i<=n;i++) 
734         {
735             if(f[i][t]<g[i][t]&&(i==s||pre[i]!=-1)) 
736             { 
737                 int v,low=g[i][t]-f[i][t]; 
738                 pre[t]=i; 
739                 for(v=t;pre[v]!=-1;v=pre[v]) 
740                     low=low<g[pre[v]][v]-f[pre[v]][v]?low:g[pre[v]][v]-f[pre[v]][v]; 
741                 if(low==0)continue; 
742                 for(v=t;pre[v]!=-1;v=pre[v]) 
743                 { 
744                     f[pre[v]][v]+=low; 
745                     f[v][pre[v]]-=low; 
746                 } 
747                 ans+=low; 
748             } 
749         }
750     } 
751     return ans;
752 }  
753 
754 int main(){
755     int m,n,i,j,u,v,w;
756     while(cin >> m >> n){
757         memset(g,0,sizeof(g));
758         for(i=0;i<m;i++){
759             scanf("%d%d%d",&u,&v,&w);
760             g[u][v]+=w;
761         }
762         cout << dinic(n,1,n) << endl;
763     }
764 }
765 【最小费用最大流】Edmonds Karp对偶算法
766 #define M 211
767 #define LIM 99999999
768 //【最小费用最大流】Edmonds Karp对偶算法,复杂度 O(V^3E^2)。返回最大流,输入图
769 //容量矩阵g[M][M],费用矩阵w[M][M],取非零值表示有边，s为源点，t为汇点，f[M][M]返
770 //回流量矩阵，minw返回最小费用。
771 int g[M][M],w[M][M],minw,f[M][M];
772 int DualityEdmondsKarp(int n,int s,int t){    
773     int i,j,k,c,quit,flow=0;
774     int best[M],prev[M];
775     minw=0;
776     for (i=1;i<=n;i++) {
777         for (j=1;j<=n;j++){
778             f[i][j]=0;
779             if (g[i][j]) {g[j][i]=0;w[j][i]=-w[i][j];}
780         }
781     }
782     while (1) {
783         for (i=1;i<=n;i++) best[i]=LIM;
784         best[s]=0;
785         do {
786             quit=1;
787             for (i=1;i<=n;i++){
788                 if (best[i]<LIM)
789                     for (j=1;j<=n;j++){
790                         if (f[i][j]<g[i][j] && best[i]+w[i][j]<best[j]){
791                             best[j]=best[i]+w[i][j];
792                             prev[j]=i;
793                             quit=0;
794                         }
795                     }
796             }
797         }while(!quit);
798         if (best[t]>=LIM) break;
799         c=LIM;
800         j=t;
801         while (j!=s) {
802             i=prev[j];
803             if (c>g[i][j]-f[i][j]) c=g[i][j]-f[i][j];
804             j=i;
805         }
806         j=t;
807         while (j!=s) {
808             i=prev[j];
809             f[i][j]+=c;
810             f[j][i]=-f[i][j];
811             j=i;
812         }
813         flow+=c; minw+=c*best[t];
814     }
815     return flow;
816 }
817