样例10超时,其他全过了,救救孩子

P3376 【模板】网络最大流

a836568125 @ 2024-10-09 19:10:46

#include<bits/stdc++.h>
using namespace std;

int n,m,s,t;
int cnt=0;

struct edge{
    int to;
    int next;
    long long capacity;
    edge(int to,int next,long long c):to(to),next(next),capacity(c){}
};

vector<int>head;
vector<edge>edges;

vector<int>level;

void add(int u,int v,long long c){
    edges.push_back(edge(v,head[u],c));
    head[u]=cnt;
    cnt++;
}

void addedges(int u,int v,long long c){
    add(u,v,c);
    add(v,u,0);
}

bool bfs(int s,int t){
    level.assign(head.size(), -1);
    level[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();

        for(int i=head[u];i!=-1;i=edges[i].next){
            edge e=edges[i];
            if(level[e.to]==-1&&e.capacity>0){
                q.push(e.to);
                level[e.to]=level[u]+1;
            }
        }
    }
    return level[t] != -1;
}

long long dfs(int s,int t ,long long flow){
    if(s==t)
        return flow;
    long long ans=0;
    for(int i=head[s];i!=-1;i=edges[i].next){
        edge & e=edges[i];
        if(e.capacity > 0 && (level[e.to] == level[s] + 1)){
            long long f = dfs(e.to,t,min(flow,e.capacity));
            ans+=f;
            e.capacity-=f;
            edges[i^1].capacity+=f;
            flow-=f;
            if(flow==0)
                break;
        }
    }
    return ans;

}

long long maxFlow(int s, int t) {
    long long ans = 0;
    while (bfs(s, t)) {
        while (true) {
            long long f = dfs(s, t, LLONG_MAX);
            if (f == 0) {
                break;
            }
            ans += f;
        }
    }
    return ans;
}

int main(){
    cin>>n>>m>>s>>t;

    head.assign(n+1,-1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        addedges(u, v, c);
    }
    cout << maxFlow(s, t) << endl;
    return 0;
}

by Joe2011 @ 2024-10-13 17:31:39

Cu ball


|