Min-Cut (Dinic with edge list) with the least number of edges possible. (COJ - 2065)

dinic-mincut.cpp

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
using namespace std;
#define MAX 5010
struct edge {
    int from,to,cap,flow;
    edge(int from, int to, int cap, int flow) :
        from(from), to(to), cap(cap), flow(flow) {}
};
int p[MAX],q[MAX];
int main() {
    int n,m;
    while (scanf("%d%d",&n,&m) != EOF) {
        const int source=1,sink=n;
        vector<edge> el;
        vector<int> ri(2*m+1);
        vector<vector<int> > graph(n+1);
        for (int i=0;i<m;i++) {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            graph[a].push_back(el.size());
            ri[el.size()+1]=el.size();
            el.push_back(edge(a,b,c*(m+1)+1,0));
            ri[el.size()-1]=el.size();
            graph[b].push_back(el.size());
            el.push_back(edge(b,a,c*(m+1)+1,0));
        }
        long long mf=0;
        while (true) {
            memset(p,-1,(n+1)*sizeof(p[0]));
            p[source]=INT_MAX;
            int head=0,tail=0;
            q[tail++]=source;
            while (head<tail) {
                int u=q[head++];
                for (int i=0;i<graph[u].size();i++) {
                    int idx=graph[u][i], to=el[idx].to;
                    if (p[to]==-1 && el[idx].cap-el[idx].flow>0) {
                        p[to]=idx;
                        q[tail++]=to;
                    }
                }
            }
            if (p[sink]!=-1) {
                long long pushed=0;
                for (int i=0;i<graph[sink].size();i++) {
                    int idx=ri[graph[sink][i]],from=el[idx].from,
                        push=el[idx].cap-el[idx].flow, v=el[idx].from;
                    while (p[v]!=INT_MAX) {
                        push=min(push,el[p[v]].cap-el[p[v]].flow);
                        v=el[p[v]].from;
                    }
                    if (!push) continue;
                    v=el[idx].from;
                    while (p[v]!=INT_MAX) {
                        el[p[v]].flow+=push;
                        el[ri[p[v]]].flow-=push;
                        v=el[p[v]].from;
                    }
                    el[idx].flow+=push;
                    el[ri[idx]].flow-=push;
                    pushed+=push;
                }
                mf+=pushed;
            } else { break; }
        }
        
        int tunnels=0;
        for (int i=1;i<=n;i++) {
            if (p[i]==-1) continue;
            for (int j=0;j<graph[i].size();j++) {
                int idx=graph[i][j];
                edge e=el[idx];
                if (p[e.to]==-1) tunnels++;
            }
        }
        
        printf("%lld %d\n", (mf/(m+1)), tunnels);
    }
    return 0;
}