dicnic还能写炸？
by shadowice1984 @ 2018-03-13 21:51:04
%%%Orz
by BriMon @ 2018-03-13 21:51:48
```c
struct data{int v;int nxt;int cot;}edge[M];
int alist[N];int cnt=1;int res;
inline void add(int u,int v,int cot)
{
edge[++cnt].v=v;edge[cnt].nxt=alist[u];alist[u]=cnt;edge[cnt].cot=cot;
edge[++cnt].v=u;edge[cnt].nxt=alist[v];alist[v]=cnt;edge[cnt].cot=0;
}
int dep[N];queue <int> q;int ctt;int s;int t;
inline bool bfs()
{
for(int i=1;i<=ctt;i++){dep[i]=0x3f3f3f3f;}
dep[s]=0;q.push(s);
while(!q.empty())
{
int now=q.front();q.pop();int nxt=alist[now];
while(nxt)
{
int v=edge[nxt].v;int cot=edge[nxt].cot;
if(dep[v]==0x3f3f3f3f&&cot!=0)
{dep[v]=dep[now]+1;q.push(v);}
nxt=edge[nxt].nxt;
}
}return dep[t]!=0x3f3f3f3f;
}
inline int dfs(int x,int lim)
{
if(x==t){return lim;}
int nxt=alist[x];int nowflow=0;
while(nxt)
{
if(lim==0)break;
int v=edge[nxt].v;int cot=edge[nxt].cot;
if(dep[v]==dep[x]+1&&cot!=0)
{
int del=dfs(v,min(lim,cot));
lim-=del;nowflow+=del;
edge[nxt].cot-=del;edge[nxt^1].cot+=del;
}nxt=edge[nxt].nxt;
}if(nowflow==0){dep[x]=0x3f3f3f3f;}
return nowflow;
}
```
```C
while(bfs()){res+=dfs(s,0x3f3f3f3f);}
```
by shadowice1984 @ 2018-03-13 21:52:27
核心代码，拿好不谢233
by shadowice1984 @ 2018-03-13 21:52:59
写SAP吧，改良后的SAP既短又快。23333
by 落寞音箫 @ 2018-03-13 21:56:52
@[cn：苏卿念](/space/show?uid=57699)
```cpp
inline int sap(int u,int maxflow){
if(u==ed)return maxflow;
int addflow=maxflow,f;
for(re int i=head[u];i;i=edges[i].last){
int to=edges[i].to;
if(d[u]==d[to]+1&&edges[i].flow){
int f=isap(to,Min(addflow,edges[i].flow));
addflow-=f;
edges[i].flow-=f;
edges[i^1].flow+=f;
if(!addflow)return maxflow;
}
}
if(!--gap[d[u]])d[st]=n;
++gap[++d[u]];
return maxflow-addflow;
}
int main({
n=read(),m=read(),st=read(),ed=read();
For(i,1,m)add(read(),read(),read());
gap[0]=n;
while(d[st]<n)ans+=isap(st,1e9);
printf("%d\n",ans);
```
by 落寞音箫 @ 2018-03-13 21:58:45
dfs有问题
by sigland @ 2018-03-13 22:14:34
~~突然想到有大佬发明了20行最大流~~
by 权御天下 @ 2018-03-13 22:25:55