RE 求助

P3376 【模板】网络最大流

_fewq @ 2023-08-19 23:14:37

https://www.luogu.com.cn/record/121855834

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=222;
struct Edge{
    int v,w;
    Edge* inv;
};
vector<Edge> G[N];
int n,m,bg,ed,pre[N],vis[N],tot,flag,ans;
Edge* pree[N];
queue<int> q;
void bfs(){
    flag=0;
    vis[bg]=++tot;
    q.push(bg);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(Edge& v:G[u]){
            if(vis[v.v]!=tot && v.w){
                vis[v.v]=tot;
                pre[v.v]=u;
                pree[v.v]=&v;
                q.push(v.v);
                if(v.v==ed){flag=1;break;}
            }
        }
    }
    if(flag){
        int tmn=0x3f3f3f3f3f3f3f3f;
        for(int i=ed;i!=bg;i=pre[i]) tmn=min(tmn,pree[i]->w);
        for(int i=ed;i!=bg;i=pre[i]) pree[i]->w-=tmn,pree[i]->inv->w+=tmn;
        ans+=tmn;
    }
    queue<int>().swap(q);
}
signed main(){
    cin >> n >> m >> bg >> ed;
    while(m--){
        int u,v,w;
        cin >> u >> v >> w;
        G[u].push_back({});
        G[v].push_back({});
        G[u].rbegin()->v=v,G[u].rbegin()->w=w,G[u].rbegin()->inv=&*G[v].rbegin();
        G[v].rbegin()->v=u,G[v].rbegin()->w=0,G[v].rbegin()->inv=&*G[u].rbegin();
    }
    do{bfs();}while(flag);
    cout << ans << endl;
    return 0;
}

一个能让自己程序 RE 的数据:(洛谷 IDE 不会 RE,本地会 RE)

3 3 1 3
1 2 1
1 3 1
2 3 1

by AAA404 @ 2023-08-20 09:09:12

@qwef_ 啊?您在写我看书都看不懂的东西


by _fewq @ 2023-08-20 09:15:01

此贴结,原因是

G[u].rbegin()->v=v,G[u].rbegin()->w=w,G[u].rbegin()->inv=&*G[v].rbegin();
G[v].rbegin()->v=u,G[v].rbegin()->w=0,G[v].rbegin()->inv=&*G[u].rbegin();

vector 动态开点时会把原来的一段内存释放,而结构体里面的指针还指向原来那段内存(


|