Dinic，如何优雅的 13 行写一个 Dinic。

提前在这里预声明：强烈谴责说我乱压行的人，显然我并没有除了 for 循环 以外一行有两个分号，而且并没有暴力压行。

下面是普通的Dinic:

inline bool bfs(){
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(s);dis[s]=0;cur[s]=head[s];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(e[i].w>0&&dis[v]==INF){
                dis[v]=dis[u]+1;
                q.push(v);cur[v]=head[v];
                if(v==t)return 1;
            }
        }
    }
    return 0;
}

inline long long dfs(int u,long long lim){
    if(u==t)return lim;
    long long temp,flow=0;
    for(int i=cur[u];i&&lim;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].to;
        if(e[i].w>0&&dis[v]==dis[u]+1){
            temp=dfs(v,min(lim,e[i].w));
            if(!temp)dis[v]=INF;
            e[i].w-=temp;e[i^1].w+=temp;
            flow+=temp;lim-=temp;
        }
    }
    return flow;
}

额，这个 Dinic 可能已经比许多人的代码短了，但是它还是有将近 30 行的长度，那么我们如何压行呢。

首先，我们并不能像某些人一样压行压到其他人都看不懂，而且一点都不美观，我们不需要暴力压行。

其次，我们不应该在增大代码的时间复杂度的情况下进行，这样没有任何好处。

好了，下面是 13 行的 Dinic 代码：

inline bool bfs() {
    int hed=1, tail=0, u;
    memset(dis, 0x3f, sizeof(dis)), q[++tail] = s, dis[s] = 0, cur[s] = head[s];
    while(hed <= tail && (u = q[hed++]))
        for(int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
            if(e[i].w > 0 && dis[v] == INF && (dis[v] = dis[u] + 1) && (q[++tail] = v) && (cur[v] = head[v]) && v == t) return 1;
    return 0;
}
inline long long dfs(int u, long long lim) {
    if(u == t) return lim;
    for(long long i = cur[u], v = e[i].to, temp, flow = 0; i && lim; i = e[i].nxt, v = e[i].to)
        if((((cur[u] = i) && e[i].w > 0 && dis[v] == dis[u] + 1 && (temp = dfs(v, min(lim, e[i].w))) && ((e[i].w -= temp) || 1) && ((e[i^1].w += temp) || 1) && ((flow += temp) || 1) && ((lim -= temp) || 1) && !temp && (dis[v] = INF)) || 1) && (!e[i].nxt || !lim)) return flow;
}

相信张大仙一定可以压的更短。

不懂的可以问张大仙。

提醒一下： 千万不要在考场上干这件事，否则你可能会收获到0分的好成绩。

由于压行之后实在太挤了，所以我打空格了 ??

然后由于 STL queue 的成员函数没有返回值不能放在 if 里面，所以要手写。

UPD:更新了一下，压到 13 行了。

Dinic，如何优雅的 13 行写一个 Dinic。

原文：https://www.cnblogs.com/Midoria7/p/13961984.html