刚学OI,TLE求助

P3376 【模板】网络最大流

bellmanford @ 2019-08-11 12:22:16

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define OPTIMIZE ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define In inline
#define Re register
#define db double
#define ll long long
const int M=1e5+5;

int n,m,s,t,tot=0,ans=0,liu[M],pre[M],first[M];
bool vis[M];
struct Edge{
    int nxt,to,val;
}e[M<<1];

int read(){
    int x=0,y=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') y=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*y;
}

void add(int x,int y,int z){
    tot++;
    e[tot].nxt=first[x];
    first[x]=tot;
    e[tot].to=y;
    e[tot].val=z;
}

bool bfs(){
    queue<int> Q;
    memset(vis,0,sizeof(vis));
    Q.push(s);
    vis[s]=1;
    liu[s]=1<<30;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=first[u];i;i=e[i].nxt){
            int v=e[i].to,w=e[i].val;
            if(!vis[v]&&w){
                vis[v]=1;
                pre[v]=i;
                liu[v]=min(liu[u],w);
                Q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}

void EK(){
    while(bfs()){
        int u=t;
        while(u!=s){
            e[pre[u]].val-=liu[t];
            e[pre[u]^1].val+=liu[t];
            u=e[pre[u]^1].to;
        }
        ans+=liu[t];
    }
}

int main(){
    n=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,0);
    }
    EK();
    printf("%d\n",ans);
}

by bellmanford @ 2019-08-11 12:22:52

写错了

是死循环


by Kevin_Wa @ 2019-08-11 12:38:03

红名去你的刚学OI


by bellmanford @ 2019-08-11 12:38:38

才几个月也算是啦QwQ


by bellmanford @ 2019-08-11 12:39:57

QAQ没有人呐


by bellmanford @ 2019-08-11 12:41:04

窝才打卡11天就红了耶


by Happynewyear @ 2019-08-11 12:42:02

红名去你的刚学OI


by pjykk @ 2019-08-11 12:43:07

刚学OI就学EK的dalao


by 表白 @ 2019-08-11 12:43:37

我也刚学,请问你这是死循环了吗


by bellmanford @ 2019-08-11 12:44:07

@表白 嗯嗯嗯


by wkywkywky @ 2019-08-11 12:46:15

去你的刚学OI


| 下一页