bramasole @ 2019-04-25 16:11:04

by kfhkx @ 2019-04-25 16:12:00

希望更丰富的展现？使用Markdown

by bramasole @ 2019-04-25 16:28:32

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100;
const int INF=(1<<30)-1;
int N,M,S,T;
int g[maxn][maxn];
int f[maxn][maxn];
int pre[maxn];
bool vis[maxn];
bool bfs(int s,int t){
    memset(pre,-1,sizeof(pre));
    memset(vis,false,sizeof(vis));
    queue<int> q;
    vis[s]=true;
    q.push(s);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=1;i<=N;i++){
            if(!vis[i]&&g[now][i]>0){
                vis[i]=true;
                pre[i]=now;
                if(i==t) return true;
                q.push(i);
            }
        }
    }
    return false;
}

int EK(int s,int t){
    int v,w,d,maxflow;
    maxflow=0;
    while(bfs(s,t)){
        v=t;
        d=INF;
        while(v!=s){
             w=pre[v];
            if(d>g[w][v]){
                d=g[w][v];
            }
            v=w;
        }
        maxflow+=d;
        v=t;
        while(v!=s){
            w=pre[v];
            g[w][v]-=d;
            g[v][w]+=d;
            if(f[v][w]>0)
                f[v][w]-=d;
            else f[w][v]+=d;
            v=w;
        }
    }
    return maxflow;
}

int main(){
    int u,v,w;
    memset(g,0,sizeof(g));
    memset(f,0,sizeof(f));
    cin>>N>>M>>S>>T;
    for(int i=1;i<=M;i++){
        cin>>u>>v>>w;
        g[u][v]+=w;
    }
    cout<<EK(S,T)<<endl;
    return 0;
}

by bramasole @ 2019-04-25 16:29:11

@kfhkx 第一次用，谢谢指导

by 龙之吻—水货 @ 2019-04-25 16:44:03

@bramasole 编译器还是有点智能的，如果你的代码需要几百个G的内存，编译器当然不会把它编译出来然后炸掉你的电脑 QwQ

by bramasole @ 2019-04-25 16:51:28

@龙之吻—水货 呃，那要怎么改进？

by 龙之吻—水货 @ 2019-04-25 16:55:55

@bramasole 用邻接表或者前向星存图 OwO

by bramasole @ 2019-04-25 18:28:23

@龙之吻—水货 ?，感谢大佬！