loj 101 最大流

冬令营送到我脸上的20分都没拿全

心态爆炸

冬令营前一天学的dinic

后一天才发出来

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define inf 2139062143

 #define ll long long

 #define MAXN 1000100

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 struct Dinic

 {

     int fst[MAXN],nxt[MAXN<<],to[MAXN<<],val[MAXN<<],cnt,n,m,s,t;

     Dinic() {cnt=;memset(fst,0xff,sizeof(fst));}

     void add(int u,int v,int w) {nxt[cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt++]=w;}

     int q[MAXN],dep[MAXN],cur[MAXN],vis[MAXN],tot;

     int BFS()

     {

         int l=,r=;

         memset(dep,0xff,sizeof(dep));

         vis[t]=++tot,q[++r]=t;

         while(l<=r)

         {

             int x=q[l++];cur[x]=fst[x];

             for(int i=fst[x];i!=-;i=nxt[i])

             {

                 if(val[i^]&&vis[to[i]]!=tot)

                 {

                     vis[to[i]]=tot,dep[to[i]]=dep[x]+,q[++r]=to[i];

                     if(to[i]==s) return ;

                 }

             }

         }

         return vis[s]==tot;

     }

     int DFS(int x,int a)

     {

         if(x==t||!a) return a;

         int flow=,f;

         for(int& i=cur[x];i!=-;i=nxt[i])

         {

             if(val[i]&&dep[to[i]]==dep[x]-&&(f=DFS(to[i],min(a,val[i]))))

             {

                 val[i]-=f,val[i^]+=f,flow+=f,a-=f;

                 if(!a) break;

             }

         }

         return flow;

     }

     ll solve()

     {

         ll ans=;int f;

         while(BFS())

         {

             memcpy(cur,fst,sizeof(cur));

             while(f=DFS(s,inf)) ans+=f;

         }

         return ans;

     }

 }D;

 int main()

 {

     int k;

     D.n=read(),k=D.m=read(),D.s=read(),D.t=read();

     int u,v,w;

     for(int i=;i<=k;i++) {u=read(),v=read(),w=read();D.add(u,v,w);D.add(v,u,);}

     printf("%lld",D.solve());

 }