dinic算法用于解决最大流问题。

注意每次BFS之前把dist数组清空，源点的dist设为1。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define inf 1000000000 5 using namespace std; 6 int ans,tot,vert,edg,S,T,fr[100005],to[200005],nxt[200005],f[200005]; 7 int que[100005],dist[100005]; 8 bool inq[100005]; 9 void adde(int p,int q,int F)10 {to[tot]=q;f[tot]=F;nxt[tot]=fr[p];fr[p]=tot++;}11 bool bfs();12 int dfs(int,int);13 int main()14 {15     memset(fr,-1,sizeof(fr));16     scanf("%d%d%d%d",&vert,&edg,&S,&T);17     int p,q,w,i;18     for(i=1;i<=edg;i++)19     {20         scanf("%d%d%d",&p,&q,&w);21         adde(p,q,w); adde(q,p,0);22     }23     while(bfs()) ans += dfs(S,inf);24     printf("%d",ans);25     return 0;26  } 27  bool bfs()28  {29      memset(dist,0,sizeof(dist));30      int l=0,r=0,i,t,now;31      que[++r] = S; dist[S] = 1;32      while(l