数据略水..

P3376 【模板】网络最大流

officeyutong @ 2017-11-30 22:13:11

Edmonds-Karp算法都可以过..

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::queue;
using std::memset;
using std::min;
using int_t = long long int;

struct Edge {
    int_t from;
    int_t to;
    int_t capacity = 0;
    int_t flow = 0;
    Edge(int_t from, int_t to, int_t capacity, int_t flow) :
    from(from), to(to), capacity(capacity), flow(flow) {
    }

};
vector<Edge> edges;
vector<int_t> graph[100000 + 1];

void insertEdge(int_t from, int_t to, int_t capacity) {
    edges.push_back((Edge){from, to, capacity, 0});
    edges.push_back((Edge){to, from, 0, 0});
    graph[from].push_back(edges.size() - 2);
    graph[to].push_back(edges.size() - 1);
}
int_t n, m, start, target;
int_t minFlow[100000 + 1];
int_t path[100000 + 1];

int main() {
    cin >> n >> m >> start>>target;
    for (int_t i = 1; i <= m; i++) {
        int_t from, to, cap;
        cin >> from >> to>>cap;
        insertEdge(from, to, cap);
    }
    int_t maxFlow = 0;
    while (true) {
        //BFS
        queue<int_t> qu;
        qu.push(start);
        memset(minFlow, 0, sizeof (minFlow));
        minFlow[start] = 0x7fffffff;
        memset(path, 0, sizeof (path));
        while (qu.empty() == false) {
            int_t x = qu.front();
            qu.pop();
            for (int_t edgeId : graph[x]) {
                Edge& edge = edges[edgeId];
                if (minFlow[edge.to] == 0 && edge.flow < edge.capacity) {
                    minFlow[edge.to] = min(minFlow[x], edge.capacity - edge.flow);
                    qu.push(edge.to);
                    path[edge.to] = edgeId;
                }
            }
            if (minFlow[target]) {
                break;
            }
        }
        if (minFlow[target] == 0)break;
 //       cout << "一条增广路" << endl;
        for (int_t v = target; v != start; v = edges[path[v]].from) {
            edges[path[v]].flow += minFlow[target];
            edges[path[v]^1].flow -= minFlow[target];
       //     cout << v << " <- ";
        }
       // cout << start<<endl;
        maxFlow += minFlow[target];
    }
    cout << maxFlow;

}

by 权御天下 @ 2017-11-30 22:18:15

@officeyutong 666(虽然我还是搞不懂大佬们为什么放着现成模板算法不写去搞别的算法...)


by DFPMTS @ 2017-11-30 22:25:31

模板还要卡岂不是太丧病了。。


by 权御天下 @ 2017-11-30 22:27:43

@DFPMTS 我还有个问题为什么所有被喷数据水的几乎都是Hansbug的题233


by officeyutong @ 2017-11-30 22:32:50

@权御天下 edmonds karp算法是最基础也是最慢的增广路算法吧..我刚学网络流233


by 权御天下 @ 2017-11-30 22:35:05

@officeyutong 所以我还是不理解您放着网络流不用用E-K的行为...


by Night_Aurora @ 2017-12-01 11:33:37

@权御天下 说得好像EK不是网络流算法似的


|