WA 80 求助

qwq___qaq @ 2023-05-12 00:13:38

6 7 1 6
1 2 1
2 4 1
4 6 1
1 3 1
3 4 1
2 5 1
5 6 1

by qwq___qaq @ 2023-05-12 00:13:51

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
int n,m,s,t,ans,delta,w[205][205],f[205][205],pre[205];
bool vis[205];
struct edge{
    int to,val;
};
vector<edge> G[205];
struct node{
    int u,del;
};
void update(int u){
    G[pre[u]][f[u][pre[u]]].val-=delta;
    cout<<u<<' '<<pre[u]<<endl;
    if(pre[u]!=s)
        update(pre[u]);
}
queue<node> q;
inline bool EK(){
    memset(vis,0,sizeof(vis)); 
    while(q.size())
        q.pop();
    q.push(node({s,inf}));
    while(q.size()){
        int u=q.front().u,val=q.front().del;
        q.pop();
        for(auto N:G[u]){
            int v=N.to,w=N.val;
            if(!w)
                continue;
            if(vis[v])
                continue;
            vis[v]=1;
            pre[v]=u;
            if(v==t){
                delta=min(val,w);
                return 1;
            }
            q.push(node({v,min(val,w)}));
        }
    }
    return 0;
}
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(int i=1,u,v,val;i<=m;++i){
        scanf("%lld%lld%lld",&u,&v,&val);
        w[u][v]+=val;
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(w[i][j])
                f[j][i]=G[i].size(),G[i].push_back(edge({j,w[i][j]}));
    while(EK())
        update(t),ans+=delta;
    printf("%lld\n",ans);
    return 0;
}