冬令营送到我脸上的20分都没拿全
心态爆炸
冬令营前一天学的dinic
后一天才发出来
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #define inf 213906214310 #define ll long long11 #define MAXN 100010012 using namespace std;13 inline int read()14 {15 int x=0,f=1;char ch=getchar();16 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}17 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}18 return x*f;19 }20 struct Dinic21 {22 int fst[MAXN],nxt[MAXN<<3],to[MAXN<<3],val[MAXN<<3],cnt,n,m,s,t;23 Dinic() {cnt=0;memset(fst,0xff,sizeof(fst));}24 void add(int u,int v,int w) {nxt[cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt++]=w;}25 int q[MAXN],dep[MAXN],cur[MAXN],vis[MAXN],tot;26 int BFS()27 {28 int l=1,r=0;29 memset(dep,0xff,sizeof(dep));30 vis[t]=++tot,q[++r]=t;31 while(l<=r)32 {33 int x=q[l++];cur[x]=fst[x];34 for(int i=fst[x];i!=-1;i=nxt[i])35 {36 if(val[i^1]&&vis[to[i]]!=tot) 37 {38 vis[to[i]]=tot,dep[to[i]]=dep[x]+1,q[++r]=to[i];39 if(to[i]==s) return 1;40 }41 }42 }43 return vis[s]==tot;44 }45 int DFS(int x,int a)46 {47 if(x==t||!a) return a;48 int flow=0,f;49 for(int& i=cur[x];i!=-1;i=nxt[i])50 {51 if(val[i]&&dep[to[i]]==dep[x]-1&&(f=DFS(to[i],min(a,val[i]))))52 {53 val[i]-=f,val[i^1]+=f,flow+=f,a-=f;54 if(!a) break;55 }56 }57 return flow;58 }59 ll solve()60 {61 ll ans=0;int f;62 while(BFS())63 {64 memcpy(cur,fst,sizeof(cur));65 while(f=DFS(s,inf)) ans+=f;66 }67 return ans;68 }69 }D;70 int main()71 {72 int k;73 D.n=read(),k=D.m=read(),D.s=read(),D.t=read();74 int u,v,w;75 for(int i=1;i<=k;i++) {u=read(),v=read(),w=read();D.add(u,v,w);D.add(v,u,0);}76 printf("%lld",D.solve());77 }