TLE......

P3376 【模板】网络最大流

YCS_GG @ 2017-11-09 21:12:24

标准dinic

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
struct Edge{
    int v;
    int w,next;
}edge[100010];
int head[100010],level[100010];
inline void read(int &x){
    x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
}
int n,m,ans,num=1;
void add(int u,int v,int w){
    edge[++num].v=v;
    edge[num].w=w;
    edge[num].next=head[u];
    head[u]=num;
    edge[++num].v=u;
    edge[num].w=0;
    edge[num].next=head[v];
    head[v]=num;
}
bool bfs(int s,int t){
    queue<int> q;
    memset(level,0,sizeof(level));
    q.push(s);
    level[s]=1;
    while(!q.empty()){
        int qnow=q.front();
        q.pop();
        for(int i=head[qnow];i!=-1;i=edge[i].next){
            if(!level[edge[i].v]&&edge[i].w!=0){
                level[edge[i].v]=level[qnow]+1;
                if(edge[i].v==t)
                    return true;
                q.push(edge[i].v);
            }
        }
    }
    return false;
}
int dfs(int x,int maxflow,int t){
    if(x==t||maxflow==0)
        return maxflow;
    int used=0;
    for(int i=head[x];i!=-1;i=edge[i].next){
        if(level[edge[i].v]==level[x]+1&&edge[i].w){
            int flow=dfs(edge[i].v,min(maxflow,edge[i].w),t);
            //if(flow==0)
                //level[edge[i].v]=0;
            used+=flow;
            maxflow-=flow;
            edge[i].w-=flow;
            edge[i^1].w+=flow;
        }
    }
    return used;
}
void Dinic(int s,int t){
    while(bfs(s,t)){
        ans+=dfs(s,0x3f3f3f3f,t);
    }
}
int main(){
    int s,t;
    read(n);
    read(m);
    read(s);
    read(t);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++){
        int u,v,w;
        read(u);
        read(v);
        read(w);
        add(u,v,w);
    }
    Dinic(s,t);
    cout<<ans;
}

by ZlycerQan @ 2017-11-09 21:15:04

您数组开小了吧。。。。


by YCS_GG @ 2017-11-09 21:38:20

谢谢.......de了半天


|