网络流

匈牙利算法最大流FF算法Dinic算法

匈牙利算法

拆散别人，成就自己

int find(int x)//对应x男生 { for(int i=1; i<=n; i++)//遍历所有女生 { if(way[x][i]&&!used[i])//男生喜欢女生，且该女生在当前匹配中未被尝试 { used[i]=1; if(girls[i]==0||find(girls[i])) { girls[i]=x; return 1; } } } return 0; }

最大流

FF算法

通过遍历所有可行的道路，更新最大流量 核心代码：

int dfs(int u,LL flow) { if(u==t)//如果到达汇点 return flow; vis[u]=true; for(int p=first[u];p;p=nxt[p])//遍历所有的能到的点 { int v=to[p]; if(val[p]==0 || vis[v])//无残量 continue; int res=0; if((res=dfs(v,min(flow,val[p])))>0) { val[p]-=res; val[p^1]+=res; return res; } } return 0; }

上述代码存在走远路，绕回的情况，故采用dinic算法，使用bfs对点进行分层，然后按照层数进行累加。

Dinic算法

void bfs() { memset(dep, 0, (n + 1) * sizeof(int));//记得开局先初始化 q[l=r=1]=s;//起始点 dep[s] = 1; while(l<=r) { int q=