网络流64分

P3376 【模板】网络最大流

Textbook_blasphemy @ 2021-05-16 16:37:35

code

#include<bits/stdc++.h>
using namespace std;
const long long inf=1<<29, N=3000010;
int head[N],d[N];
long long n, m, s, t, tot, max_flow;
queue<long long> q;
struct node{
    long long to;
    long long next;
    long long dis;
}edge[N];
void add(long long x,long long y,long long z) {
    edge[++tot].dis=y;
    edge[tot].to=z;
    edge[tot].next=head[x];
    head[x]=tot;
    edge[++tot].dis=x;
    edge[tot].to=0;
    edge[tot].next=head[y];
    head[y]=tot;
}
long long bfs(){
    memset(d,0,sizeof(d));
    while(q.size())q.pop();
    q.push(s); 
    d[s]=1;
    while(q.size()){
        long long x=q.front();
        q.pop();
        for(long long i=head[x];i;i=edge[i].next)
            if(edge[i].to&&!d[edge[i].dis]){
                q.push(edge[i].dis);
                d[edge[i].dis]=d[x]+1;
                if(edge[i].dis==t)return 1;
            }
    }
    return 0;
}
long long dinic(long long x,long long flow){ 
    if(x==t)return flow;
    long long rest=flow,k;
    for(long long i=head[x];i&&rest;i=edge[i].next)
        if(edge[i].to&&d[edge[i].dis]==d[x]+1){
            k=dinic(edge[i].dis,min(rest,edge[i].to));
            if(!k)d[edge[i].dis]=0;
            edge[i].to-=k;
            edge[i^1].to+=k;
            rest-=k;
        }
    return flow-rest;
}
int main(){
    //freopen("P3376_7.txt","r",stdin);
    scanf("%lld%lld",&n,&m);
    scanf("%lld%lld",&s,&t);
    tot=1;
    for(long long i=1;i<=m;i++){
        long long x,y,c;
        scanf("%lld%lld%lld",&x,&y,&c);
        add(x,y,c);
    }
    long long flow=0;
    while(bfs())
        while(flow=dinic(s,inf))max_flow+=flow;
    printf("%lld",max_flow);
}

我下载了第七个测试点,不加文件读入RE(return 3221225477 w(゚Д゚)w)了,加了文件读入AC了(和out文件结果一样)

求答疑


by __ZXYAKIOI__ @ 2021-05-16 17:05:35

\color{white}{qpwg}

by RinkaSnow @ 2021-05-25 21:33:04

UB


|