当前位置:编程学习 > C/C++ >>

POJ 1273 Drainage Ditches 最大流-EdmondsKarp(EK)

[cpp] 
#include <set> 
#include <map> 
#include <list> 
#include <cmath> 
#include <ctime> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <cctype> 
#include <cstdio> 
#include <string> 
#include <vector> 
#include <cassert> 
#include <cstdlib> 
#include <cstring> 
#include <sstream> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
int max(int a,int b){return a<b?b:a;} 
int min(int a,int b){return a>b?b:a;} 
#define V 205 
#define INF 0x3f3f3f3f 
int cap[V][V],flow[V][V];// cap是每条边的容量,flow是每条边的流量 
int res[V],father[V];//res[]是每个点的剩余流量,father[]是每个点的父亲 
int s,t,u,v,f=0; //f是最大流 
int m,n,a,b,c; 
int EK(int s,int t)  //白书EK模板,加点注释大家比较容易理解 

    f=0; 
    queue<int> q; 
    memset(flow ,0,sizeof(flow)); //最开始每条边的流量都是0 
    while(1) 
    { 
        memset(res,0,sizeof(res)); //残余流量得变0,一开始所有点都没流入对吧 
        res[s]=INF; //源点嘛,剩余流量无限是必须的... 
        q.push(s); //从源点开始进行BFS找增广路 
        while(!q.empty()) 
        { 
            u = q.front(); //取队头 
            q.pop(); 
            for(v=1;v<=n;v++) //遍历所有点,找可行边 
            { 
                if(!res[v] && cap[u][v]>flow[u][v])  //该点剩余流量为0 且 容量大于流量,也就是找到了新的结点 
                { 
                    father[v]=u;//找到新结点,父节点得记录一下吧 
                    q.push(v); //明显新结点要入队列 
                    res[v]=min(res[u],cap[u][v]-flow[u][v]);//如果u的剩余流量能填满uv就填满,不能的话就把u这点的流量全部流向uv 
                } 
            } 
        } 
        if(res[t]==0) //如果当前已经是最大流,汇点没有残余流量 
            return f; 
        for(u=t;u!=s;u=father[u]) //如果还能增广,那么回溯,从汇点往回更新每条走过的边的流量 
        { 
            flow[father[u]][u]+=res[t];  //更新正向流量 
            flow[u][father[u]]-=res[t];  //更新反向流量 
        }  www.zzzyk.com
        f+=res[t];  //找到可增广的流量真开心 
    } 

int main() 

    while(cin>>m>>n)//万恶多组,贡献一次WA 
    { 
        memset(cap,0,sizeof(cap)); 
        memset(flow,0,sizeof(flow)); 
        memset(father,0,sizeof(father)); 
        memset(res,0,sizeof(res)); 
        while(m--) 
        { 
            cin>>a>>b>>c; 
            cap[a][b]+=c; //万恶重边,再贡献一次WA 
        } 
        cout<<EK(1,n)<<endl; 
    } 
    return 0; 

有史以来注释最多的EK了...
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,