_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 动态开点时会把原来的一段内存释放,而结构体里面的指针还指向原来那段内存(