做不出来题所以水博客来了
先来一个Dinic板子，基本来自Yxs学长

include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=505,M=5050;
struct node{
   int from,to,next,w;
}a[2*M];
int head[N],mm=2;
inline void add(int x,int y,int z)
{
   a[mm].from=x;a[mm].to=y;a[mm].w=z;
   a[mm].next=head[x];head[x]=mm++;
}
int n,m,s,t;
int hd[N],d[N];
queue <int> q;
inline bool bfs()
{
   memset(d,0x3f,sizeof(d));
   memcpy(head,hd,sizeof(head));
   while(!q.empty())q.pop();
   q.push(s);d[s]=0;
   while(!q.empty())
   {
      int x=q.front();q.pop();
      for(int i=head[x];i;i=a[i].next)
      {
         if(!a[i].w)continue;
         int y=a[i].to;
         if(d[y]>d[x]+1)d[y]=d[x]+1,q.push(y);
      }
      if(x==t)return 1;
   }
   return 0;
}
int dfs(int x,int flow)
{
   if(x==t)return flow;
   int rest=flow,k;
   for(int i=head[x];i;head[x]=i=a[i].next)
   {
      if(!a[i].w)continue;
      int y=a[i].to;
      if(d[y]==d[x]+1)
      {
        k=dfs(y,min(a[i].w,rest));
        if(!k)d[y]=0;
        else a[i].w-=k,a[i^1].w+=k,rest-=k;
      }
      if(!rest)break;
   }
   return flow-rest;
}
signed main()
{
   cin>>n>>m>>s>>t;
   for(int i=1;i<=m;i++)
   {
      int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
      add(x,y,z);add(y,x,0);
   }
   memcpy(hd,head,sizeof(hd));
   int ans=0;
   while(bfs())ans+=dfs(s,1e18);
   cout<<ans;
   return 0;

有一个地方是学长特别强调的，就是在dfs中的时候

for(int i=head[x];i;head[x]=i=a[i].next)
   {
      if(!a[i].w)continue;
      int y=a[i].to;
      if(d[y]==d[x]+1)
      {
        k=dfs(y,min(a[i].w,rest));
        if(!k)d[y]=0;
        else a[i].w-=k,a[i^1].w+=k,rest-=k;
      }
      if(!rest)break;
   } 

这个if(!rest)break; 一定要写到循环之内，不能写在循环上面
for(int i=head[x];i&&rest;head[x]=i=a[i].next) 是错误的，会导致特别慢
还有里面这个k=dfs(y,min(a[i].w,rest)); ，要和rest取min，不能和flow取min，否则会导致算出来的最大流变大 我因为这调了一天
时间复杂度是个玄学，理论\(O(n^2m)\),实际根本跑不满，\(n=1e6\)都能1s跑完

暂时没打EK，等费用流再说吧

关于建模

1.拆点，对于一些实际问题要把点拆成两个，分别对应流入，流出，方便对其进行限制
2.二分，这部分和网络流经常结合在一起，常常是当求一个最小时间/次数时，二分一个值，然后跑最大流\(check\)，每次新建图，记得要清干净
3.对于一一对应的限制问题，建出的大多是二分图，左右各一堆点，之间连边
4.相邻之类限制考虑黑白染色建图，黑白点放在左右