2020-2021:teams:legal_string:lgwza:dinic_算法
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:dinic_算法 [2020/08/16 15:22] lgwza [Dinic 算法] |
2020-2021:teams:legal_string:lgwza:dinic_算法 [2020/08/16 15:26] (当前版本) lgwza [Dinic 算法] |
||
|---|---|---|---|
| 行 37: | 行 37: | ||
| const ll INF=0x3f3f3f3f; | const ll INF=0x3f3f3f3f; | ||
| int tot=1,head[N],cur[N],to[M],nxt[M],level[N]; | int tot=1,head[N],cur[N],to[M],nxt[M],level[N]; | ||
| - | ll val[M]; | + | ll val[M];//剩余容量 |
| bool vis[N]; | bool vis[N]; | ||
| void add(int u,int v,ll c){ | void add(int u,int v,ll c){ | ||
| 行 73: | 行 73: | ||
| } | } | ||
| ll DFS(int u,ll ret,int s,int t){ | ll DFS(int u,ll ret,int s,int t){ | ||
| - | if(u==t||ret==0) return ret; | + | if(u==t||ret==0) return ret;//ret 表示 S 到这里最多能流入的流量 |
| - | ll Flow=0,f; | + | ll Flow=0,f;//Flow 表示经过该点的所有流量和（相当于流出的总量）；f 表示当前最小的剩余容量 |
| for(int i=cur[u];i&&ret;i=nxt[i]){ | for(int i=cur[u];i&&ret;i=nxt[i]){ | ||
| - | cur[u]=i; | + | cur[u]=i;//当前弧优化 |
| int v=to[i]; | int v=to[i]; | ||
| if(level[u]+1==level[v]&&val[i]>0){ | if(level[u]+1==level[v]&&val[i]>0){ | ||
| 行 87: | 行 87: | ||
| } | } | ||
| } | } | ||
| - | return Flow; | + | return Flow;//返回实际使用的流量 |
| } | } | ||
| ll Dinic(int s,int t){ | ll Dinic(int s,int t){ | ||
2020-2021/teams/legal_string/lgwza/dinic_算法.1597562548.txt.gz · 最后更改: 2020/08/16 15:22 由 lgwza
