求救,调了一下午了,样例过了,但是全TLE,马蜂良好,悬一关

P3376 【模板】网络最大流

Silent_Ltcd_2024 @ 2023-09-02 17:39:43

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5,M=1e6+5;
int n,m,s,t,vis[N][N],V[N],pre[N];
long long dis[N],ans;
queue <int> q;
struct Edge{
    int next,to;
    long long c;
} edge[M];
int head[M],sumedge=1;
void build_edge(int from,int to,int c) {
    sumedge++;
    edge[sumedge].next=head[from];
    edge[sumedge].to=to;
    edge[sumedge].c=c;
    head[from]=sumedge;
    return;
}
bool check() {
    while(!q.empty()) q.pop();
    memset(V,0,sizeof(V));
    q.push(s),V[s]=true,dis[s]=INT_MAX;
    while(!q.empty()) {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=edge[i].next) {
            if(edge[i].c) {
                int v=edge[i].to;
                if(V[v]) continue;
                dis[v]=min(dis[u],edge[i].c),pre[v]=u;
                q.push(v),V[v]=true;
                if(v==t) return true;
            }
        }
    }
    return false;
}
void update() {
    int u=t;
    while(u!=s) {
        int v=pre[u];
        edge[v].c-=dis[t],edge[v^1].c+=dis[t];
        u=edge[v^1].to;
    }
    ans+=dis[t];
    return;
}
int main() {
    int u,v,w;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) {
        cin>>u>>v>>w;
        if(!vis[u][v]) {
            vis[u][v]=sumedge+1;
            build_edge(u,v,w),build_edge(v,u,0);
        }
        else edge[vis[u][v]].c+=w;
    }
    while(check()) update();
    cout<<ans;
    return 0;
}

by Silent_Ltcd_2024 @ 2023-09-02 17:43:44

此贴结


by Silent_Ltcd_2024 @ 2023-09-02 17:45:18

pre[v]=u 改为 pre[v]=i

原因:pre 记录的是节点 v 与其前驱的连的一条边的编号,并非其前驱。


|