最大流预习
目录前情提要：
看看人家初中，早就学完最大流最小割，还在最小费用流了，我却从来没有正式接触过
太丢脸了吧
所以今天尝试来写一下EK和DI
EK算法流程
1.初始化
2.bfs找到一条增广路
3.找到限制边残余量k,这条路上正向边都减去k,反向边残余流量都加上k。
4.重复步骤2直到不再有增广路存在
然后自己试着打了一下EK，woc竟然过了（想当年，我di写了好几万年......)
应该只有我会写这种vector的代码吧
重要代码实现：
1.vector怎么快速找反向边呢？
假设我现在已知u->v这条边我怎么快速找到v->u这条边呢？
很明显，我反向边建立的时候正是正向边建立的时候
所以，我可以记录一下对方vector存储的位置-->未存储前的size
为什么是未存前？这是因为vector是从0开始标号的，如果从1开始，我加入的这个位置肯定是size+1。
2.已知u,v，两者我都不知道具体存储位置怎么办？
这个也很简单，我利用了cb这个数组，cb(i,j)表示我第一次建立i->j这条边的时候，j存在vector(i)的哪个位置
那么很显然，这个值就是vector(i)的size
那么我利用mp(i,cb(i,j))就能找到i->j这条边具体位置
3.去重怎么办？
很明显的是同一条边具有可加性，然后判断下cb我是否已经赋值了，如果赋值了，就找到这条边然后加就行了
4.最后一定记住bfs及其小细节即可！
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int to;
int c;//最大流量
int f;//残余流量，最开始就是c
int rev;//反向边在另一个地方的编号 ,即已知边u->v：在mp[v][rev]就正好是u处，正好就是反向边
};
int n,m,s,t;
vector<node>mp[205];
vector<node>rev[205];
bool vis[205];
int dis[205];
int pre[205];
int cb[205][205];//重边可加性 ,值则是表示存储位置
int ans=0;
bool bfs(){
memset(vis,0,sizeof(vis));
queue<int>q;
vis[s]=1;
dis[s]=2005020600;//从原点到达x点的最大流
q.push(s);
while(q.size()){
int tmp=q.front();
q.pop();
for(int i=0;i<mp[tmp].size();i++){
if(mp[tmp][i].f==0){
continue;
}
int to=mp[tmp][i].to;
if(vis[to]){
continue;
}
dis[to]=min(dis[tmp],mp[tmp][i].f);//这条路我只能流他剩下的
pre[to]=tmp;
q.push(to);
vis[to]=1;
if(to==t){
return 1;
}
}
}
return 0;
}
inline void updata() { //更新所经过边的正向边权以及反向边权
int x=t;
while(x!=s) {
int to=pre[x];
int id1=cb[x][to];
mp[x][id1].f+=dis[t];
int id=mp[x][id1].rev;
mp[to][id].f-=dis[t];
x=to;
}
ans+=dis[t]; //累加每一条增广路经的最小流量值
}
void EK(){
while(bfs()!=0){
updata();
}
}
signed main(){
ios::sync_with_stdio(false);
cin >> n >> m >> s >> t;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cb[i][j]=-1;
}
}
for(int i=1;i<=m;i++){
int u,v,w;
cin >> u >> v >> w;
if(cb[u][v]==-1){
int revu=mp[u].size();
int revv=mp[v].size();
cb[u][v]=revu;
cb[v][u]=revv;
mp[u].push_back((node){v,w,w,revv});
mp[v].push_back((node){u,w,0,revu});
}
else{
int id=cb[u][v];
mp[u][id].c+=w;
mp[u][id].f+=w;
int id2=mp[u][id].rev;
mp[v][id2].c+=w;
}
}
EK();
cout<<ans;
}