凭什么??(Dinic版本)

P3376 【模板】网络最大流

Twiter_ln @ 2023-11-03 17:22:56

```cpp #include<bits/stdc++.h> // Test on : 66ms by Red_uncle using namespace std; int n,m,s,t; typedef long long ll; struct node{ int to; ll w; int nex; }e[200005]; int cnt=1; int head[200005]; ll dis[200005]; int now[200005]; int bfs(){ for(int i=1;i<=n;i++){ dis[i]=1e18; } dis[s]=0; queue<int> p; p.push(s); now[s]=head[s]; while(!p.empty()){ int top=p.front(); p.pop(); for(int i=head[top];i;i=e[i].nex){ int y=e[i].to; if(dis[y]>dis[top]+1&&e[i].w>0){ now[y]=head[y]; dis[y]=dis[top]+1; p.push(y); if(y==t){ return 1; } } } } return 0; } ll dfs(int x,ll sum){ if(x==t)return sum; ll res=0; for(int i=now[x];i&&sum>0;i=e[i].nex){ int y=e[i].to; now[x]=i; if(dis[y]==dis[x]+1&&e[i].w>0){ ll k=dfs(y,min(sum,e[i].w)); e[i].w-=k; e[i^1].w+=k; sum-=k; res+=k; } } return res; } inline void add(int u,int v,ll w){ e[++cnt].nex=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; e[++cnt].nex=head[v]; e[cnt].to=u; e[cnt].w=0; head[v]=cnt; } int main(){ cin>>n>>m>>s>>t; for(int i=1;i<=m;i++){ int x,y; ll w; cin>>x>>y>>w; add(x,y,w); } ll ans=0; while(bfs()){ // cout<<1<<" "<<ans<<'\n'; ans+=dfs(s,1e18); } cout<<ans; return 0; } ``` $而我的码这样↓,却847ms,凭什么....
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;
const int N = 207;
typedef long long lli;

int n, m, S, T;
int x, y, z;

struct pot{
    int v, nxt;
    lli val;
}E[50*N];
int head[N], tot = 1;
inline void Add_edge(int u, int v, int val) {
    E[++tot].v = v;
    E[tot].val = val;
    E[tot].nxt = head[u];
    head[u] = tot;
}

int dep[N], cur[N];
inline bool bfs() {
    queue <int> q;
    q.push(S);
    memset(dep, 0, sizeof(dep));
    dep[S] = 1;

    int u, v;
    while(q.size()) {
        u = q.front();
        q.pop();

        for(int i=head[u];i;i=E[i].nxt) {
            v = E[i].v;
            if(dep[v] || !E[i].val) continue;
            dep[v] = dep[u] + 1;
            q.push(v);
            if(v == T) return true;
        }
    }
    return false;
}
inline lli dfs(int u, lli nowflow) {
    if(u == T) return nowflow;
    if(nowflow == 0) return 0;

    int v;
    lli sum = 0, f;

    for(int i=cur[u];i;i=E[i].nxt) {
        v = E[i].v;
        cur[u] = i;
        if(dep[v] != dep[u]+1 || !E[i].val) continue;
        f = dfs(v, min(E[i].val, nowflow));
        E[i].val -= f;
        E[i^1].val += f;
        sum += f;
        nowflow -= f;
    }
    return sum;
}

void Dinic() {
    lli ans = 0;
    while(bfs()) {
        memcpy(cur, head, sizeof(cur));
        ans += dfs(S, 0x3fffffffffffffff);
    }
    printf("%lld\n", ans);
}

int main() {

    scanf("%d%d%d%d", &n, &m, &S, &T);
    for(int i=1;i<=m;++i) {
        scanf("%d%d%d", &x, &y, &z);
        Add_edge(x, y, z);
        Add_edge(y, x, 0);
    }

    Dinic();

    return 0;
}

(无语子......)


by adam01 @ 2023-11-03 17:38:00

@Twiter_ln 你 bfs 的时候没有重置当前弧(cur 数组)。


by Mikefeng @ 2023-11-03 17:41:54

@adam01 你再想想


by adam01 @ 2023-11-03 17:43:14

@Mikefeng 没事了,我瞎了。


by Mikefeng @ 2023-11-03 17:43:56

应该是 dfs 里面没有 nowflow 为 0 break,这个常数优化比较大。


by Twiter_ln @ 2023-11-03 18:51:09

@Mikefeng 有啊?

if(nowflow == 0) return 0;
这个是吗?

by reveal @ 2023-11-03 18:53:06

@Twiter_ln 不是,是

nowflow -= f; 后面需要立刻判断 nowflow==0 时退出。

否则这条弧可能因为流量不足而被跳过(但实际上还能继续推流),然后你就得到了一个常数巨大的 EK 算法。


by Twiter_ln @ 2023-11-03 18:55:32

@reveal (有道理)

但是第一份(貌似)也没有......?

by reveal @ 2023-11-03 18:57:10

贴一个 rvalue 的原话:

因为如果你不理解Dinic的过程与复杂度分析, 你几乎一 定 会 写 假.

有些看起来很不起眼的小细节可能影响着整个算法的时间复杂度.

首先就是当前弧优化的跳出条件, 我为啥要把"除了最后一条边之外"那句话加粗呢? 因为你如果把跳出判定写在 for循环里会慢 10 倍以上, 根本不是常数问题, 是复杂度出了锅. 因为你会漏掉最后那个可能没跑满的弧, 而分层图 BFS 会在当前图没有被割断的时候一直跑跑跑, 于是就锅了.


by reveal @ 2023-11-03 18:58:26

@Twiter_ln 他是在 for 中判断了流量为 0 之后在更新当前弧的,但你完全没判,所以你这就是个常数巨大的 EK,连跑不满的机会都没有。


by Twiter_ln @ 2023-11-03 19:05:09

@reveal 57ms,感谢已解决 /ws (之前不太明白:在里面和外面判断 有什么区别/wul)


|