我为什么能ac???

P3376 【模板】网络最大流

MINO1 @ 2024-10-01 23:41:13

这是oi wiki上的Dinic模板,一个月前,我把dfs中的e[i^1].flow改成了e[i|1].flow,仍然ac了这个模板题。

直到遇到codeforces 976F,被改这一下害惨了,搞了好久都没ac,因为都忘记改过了,还以为是思路有问题,看了好久才发现是模板有问题。

欢迎来hack本蒟蒻。

//code by MINO1
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 10004;
const int INF = INT_MAX;

struct MF {
    struct edge {
        int v,nxt,cap,flow;//子节点,下一条边,容量,流量
    } e[N];

    int fir[N],cnt = 0;
    int n,S,T;
    ll maxflow = 0;
    int dep[N],cur[N];

    void init(int n,int s,int t) {
        cnt = 0;maxflow = 0;
        this->n = n;this->S = s;this->T = t;
        memset(fir,-1,sizeof(int) * (n + 1));
    }

    void addedge(int u,int v,int w) {
        e[cnt] = {v,fir[u],w,0};
        fir[u] = cnt++;
        e[cnt] = {u,fir[v],0,0};
        fir[v] = cnt++;
    }

    bool bfs() {
        queue<int> q;
        memset(dep,0,sizeof(int) * (n + 1));
        dep[S] = 1;
        q.push(S);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = fir[u];~i;i = e[i].nxt) {
                int v = e[i].v;
                if (!dep[v] && e[i].cap > e[i].flow) {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
            }
        }
        return dep[T];
    }

    int dfs(int u,int flow) {
        if (u == T || !flow) return flow;
        int ret = 0;
        for (int& i = cur[u];~i;i = e[i].nxt) {
            int v = e[i].v;int d = 0;
            if (dep[v] == dep[u] + 1 && (d = dfs(v,min(flow - ret,e[i].cap - e[i].flow)))) {
                ret += d;
                e[i].flow += d;
                e[i | 1].flow -= d;
                if (ret == flow) return ret;
            }
        }
        return ret;
    }

    ll dinic() {
        while (bfs()) {
            memcpy(cur,fir,sizeof(int) * (n + 1));
            maxflow += dfs(S,INF);
        }
        return maxflow;
    }
}mf;

void solve() {
    int n,m,s,t;cin >> n >> m >> s >> t;
    mf.init(n,s,t);
    for (int i = 1;i <= m;i++) {
        int u,v,w;cin >> u >> v >> w;
        mf.addedge(u,v,w);
    }
    cout << mf.dinic() << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    solve();
}

by EasonLiang @ 2024-10-02 00:05:57


by Terrible @ 2024-10-02 00:40:05

意义不大的行为:“打破砂锅问到底”,解析一下题目目前采用的数据,考察错误情况并总结数据的某种性质。

有意义的目的:加点数据卡掉错误代码,以防后人再次掉坑。

问“为什么”要么是不清楚自己能从中得到什么,要么是表达中掩盖了一定的目的性。

为什么对个人意义不大?这会费时费力总结出来一些普遍性不是很强的结论,而且这对参加赛事来说也大可不必。


by _Ad_Astra_ @ 2024-10-02 00:48:23

@MINO1 说明数据太弱,反向边没用到过。


by Terrible @ 2024-10-02 01:04:54

洛谷很多数据都很水,而且似乎没人修的样子。

本题后面就补加了一个新测试点,真就挤牙膏呗?


by lonely_seele @ 2024-10-02 01:30:07

@Terrible 意义较大的行为:告诉大家这题数据过弱,如果你通过了这到模板题仍然需要检查自己板子的什么地方

意义微小的行为:在这个帖子下面批判楼主(当然我这条回复也是)


|