USACO 4.4 Pollutant Control

It is an obvious max flow min cut problem. The nasty part of this problems is:

• There might be multiple routes between same warehouses, so the graph might contain multiple edges between two vertices.
• The output requires to print the routes under certain constraints, instead of just asking about the min cut cost.

The idea is:

• Find the max flow first. The cost of the max flow must be min cut.
• Sort all edges in cost descending order. Then iterate through the sorted edges, do two things:
  • Remove this edge from the graph temporarily, calculate the maximum flow value. If the diff between the calculated maximum flow value and the original max flow value (the value calculated without removing the edge from the graph) is the capacity of the edge, then this edge must be in the min cut.
  • If an edge is in a min cut, remove this edge from the graph, and repeat, until we get all edges.

This code is a simple modification of the Drainage Ditches Problem Solution that fits this problem, however it does not pass all test data because it does not deal with multiple edges connecting same two vertices. Will post another solution soon.

#include <vector>
#include <iostream>
#include <fstream>
#include <climits>
#include <functional>
#include <algorithm>
#include <numeric>

using namespace std;

int N, M, Si, Ei, Ci;
struct Edge {
    int to, cap, rev, index;
    Edge(int to, int cap, int rev, int index) :
    to(to), cap(cap), rev(rev), index(index) {}
};

vector<vector<Edge>> graph;
vector<vector<Edge>> graphCopy;
vector<bool> visited;
vector<Edge*> edges;
void addEdge(int from, int to, int cap, int index) {
    graph[from].emplace_back(Edge(to, cap, (int)graph[to].size(), index));
    graph[to].emplace_back(Edge(from, 0, (int)graph[from].size() - 1, index));
}

// Ford–Fulkerson
int dfs(int v, int t, int f) {
    if (v == t)
    return f;
    visited[v] = true;
    int size = (int)graph[v].size();
    for (int i = 0; i < size; ++i) {
        auto &e = graph[v][i];
        if (visited[e.to] || e.cap <= 0) continue;
        int d = dfs(e.to, t, std::min(f, e.cap));
        if (d <= 0) continue;
        e.cap -= d;
        graph[e.to][e.rev].cap += d;
        return d;
    }
    return 0;
}

int maxFlow(int s, int t) {
    int flow = 0;
    while (true) {
        std::fill(visited.begin(), visited.end(), false);
        int f = dfs(s, t, INT_MAX);
        if (f == 0) return flow;
        flow += f;
    }
}

int main() {
    ifstream fin("milk6.in");
    ofstream fout("milk6.out");
    
    fin >> N /* warehouses - vertices */ >> M /* trucks - edges */;
    graph = vector<vector<Edge>>(N + 1, vector<Edge>());
    
    visited = vector<bool>(N + 1, false);
    for (int i = 0; i < M; ++i) {
        fin >> Si >> Ei >> Ci;
        addEdge(Si, Ei, Ci, i);
        //cout << Si << " " << Ei << " " << Ci << " " << i << endl;
    }
    
    for (int i = 0; i < N; ++i) {
        for (auto &edge : graph[i]) {
            if (edge.cap == 0) continue;
            edges.emplace_back(&edge);
        }
    }

    sort(edges.begin(), edges.end(), [] (Edge *e1, const Edge *e2) {
        return e1->cap > e2->cap;
    });
    
    graphCopy = graph;
    int ans = maxFlow(1, N);
    graph = graphCopy;
    int total = ans;

    vector<int> ret;
    for (int i = 0; i < edges.size(); ++i) {
        //cout << "cap : " << edges[i]->cap << "; index : " << edges[i]->index << endl;
        graphCopy = graph;
        int cap = edges[i]->cap;
        edges[i]->cap -= cap;
        int flow = maxFlow(1, N);
        if (ans - flow == cap) {
            ret.push_back(edges[i]->index);
            graph = graphCopy;
            ans = flow;
        } else {
            graph = graphCopy;
            edges[i]->cap += cap;
        }
    }
    
    fout << total - ans << " " << ret.size() << endl;
    for (auto val : ret) {
        fout << val + 1 << endl;
    }
}