图论：Dinic算法

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

然而并没有什么鸟用

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

模板题Codevs1993

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

建图直接Dinic下面给代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 const int INF=0x7fffffff;

 int n,m,cnt=1,ans;

 int g[maxn],q[maxn],h[maxn];

 struct Edge{int t,next,v;}e[maxn];

 void addedge(int u,int v,int w)

 {

     e[++cnt].t=v;e[cnt].next=g[u];

     g[u]=cnt;e[cnt].v=w;

 }

 bool bfs()

 {

     memset(h,-,sizeof(h));

     int t=,w=,u;

     q[t]=;h[]=;

     while(t!=w)

     {

         u=q[t];t++;

         if(t==) t=;

         for(int tmp=g[u];tmp;tmp=e[tmp].next)

         {

             if(e[tmp].v&&h[e[tmp].t]==-)

             {

                 h[e[tmp].t]=h[u]+;

                 q[w++]=e[tmp].t;

                 if(w==) w=;

             }

         }

     }

     if(h[n]==-) return ;

     return ;

 }

 int dfs(int x,int f)

 {

     if(x==n) return f;

     int w,used=;

     for(int tmp=g[x];tmp;tmp=e[tmp].next)

     {

         if(e[tmp].v&&h[e[tmp].t]==h[x]+)

         {

             w=dfs(e[tmp].t,min(f-used,e[tmp].v));

             used+=w;e[tmp].v-=w;e[tmp^].v+=w;

             if(used==f) return f;

         }

     }

     if(!used) h[x]=-;

         return used;

 }

 void dinic()

 {

     while(bfs()) ans+=dfs(,INF);

 }

 int main()

 {

     scanf("%d%d",&m,&n);

     int x,y,z;

     for(int i=;i<=m;i++)

     {

         scanf("%d%d%d",&x,&y,&z);

         addedge(x,y,z);

         addedge(y,x,);

     }

     dinic();

     printf("%d",ans);

     return ;

 }

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

别的就是直接求就好了