图论：Dinic算法

解决最大流问题我搜到了一堆的算法：EK算法、FF算法、Dinic算法、SAP算法、ISAP算法

然而并没有什么鸟用

掌握最常见的Dinic就够了，据说极限优化的ISAP比Dinic更快一些。。我当不知道好了

模板题Codevs1993

给定源点汇点，求从源点走到汇点的所有流量和，最大流就是求最大值了

建图直接Dinic下面给代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=505;
 6 const int INF=0x7fffffff;
 7 int n,m,cnt=1,ans;
 8 int g[maxn],q[maxn],h[maxn];
 9 struct Edge{int t,next,v;}e[maxn];
10 void addedge(int u,int v,int w)
11 {
12     e[++cnt].t=v;e[cnt].next=g[u];
13     g[u]=cnt;e[cnt].v=w;
14 }
15 bool bfs()
16 {
17     memset(h,-1,sizeof(h));
18     int t=0,w=1,u;
19     q[t]=1;h[1]=0;
20     while(t!=w)
21     {
22         u=q[t];t++;
23         if(t==501) t=0;
24         for(int tmp=g[u];tmp;tmp=e[tmp].next)
25         {
26             if(e[tmp].v&&h[e[tmp].t]==-1)
27             {
28                 h[e[tmp].t]=h[u]+1;
29                 q[w++]=e[tmp].t;
30                 if(w==501) w=0;
31             }
32         }
33     }
34     if(h[n]==-1) return 0;
35     return 1;
36 }
37 int dfs(int x,int f)
38 {
39     if(x==n) return f;
40     int w,used=0;
41     for(int tmp=g[x];tmp;tmp=e[tmp].next)
42     {
43         if(e[tmp].v&&h[e[tmp].t]==h[x]+1)
44         {
45             w=dfs(e[tmp].t,min(f-used,e[tmp].v));
46             used+=w;e[tmp].v-=w;e[tmp^1].v+=w;
47             if(used==f) return f;
48         }
49     }
50     if(!used) h[x]=-1;
51         return used;
52 }
53 void dinic()
54 {
55     while(bfs()) ans+=dfs(1,INF);
56 }
57 int main()
58 {
59     scanf("%d%d",&m,&n);
60     int x,y,z;
61     for(int i=1;i<=m;i++)
62     {
63         scanf("%d%d%d",&x,&y,&z);
64         addedge(x,y,z);
65         addedge(y,x,0);
66     }
67     dinic();
68     printf("%d",ans);
69     return 0;
70 }

注意Edge里面的v是容量，还有建图的时候要注意一下怎么建的

别的就是直接求就好了