USACO Training milk6

Hecking DONE with 4.4!

Attempt 1 (WA 1/12)

I tried using a straightforward max-flow min-cut as described my USACO, calculating the max flow and then enumerating over the edges in increasing weight order, testing if the removal of an edge decreases the max flow, and if so, removing this edge. 

RESULT:

After some preliminary debugging this passed the sample test case, but failed on the second case, due to the requirement that the amount of edges must be minimized.

CONTEMPLATION:

Here Teacher Huang advised me to undertake the method of "multiply input edge weight by 10000 and add 1" to account for the weighting of edge count as well, but I refused to believe this, as if we have a graph of the following edge list:

(1, 2) weight 1 -> weight 10001, i.e. edge #1

(1, 2) weight 1 -> weight 10001, i.e. edge #2

(2, 3) weight 2 -> weight 20001, i.e. edge #3

Here, the max flow is obviously 20001, but the USACO algorithm will deduce the edges #1 and #2 are the min cut. This violates the MCMF theorem, because the sum of edge weight #1 and #2 are 20002.

Attempt 2 (WA 0/12)

After some contemplating of the max flow algorithm, I "found out" (wrongly) that the min cut will always be the "critical" edges, i.e. the "limiting" edges for each flow from s to t, or the edges in the flow with least weight. Implementing this was easy, and because it passed the second test case, I assumed it would pass the first. I was wrong; I failed to consider that in a flow, a certain edge may be "expended", after having some flow pushed through it already, and become a "critical" edge in another flow. In these cases, my algorithm will add extra unnecessary edges to the min cut.

RESEARCH

From here, I strongly believed the USACO method for finding min cut was wrong. When I searched online, I found that there was a better algorithm, namely taking the residual graph of a max flow and doing a flood fill from the source, and if an input edge went from a flooded node to an unfolded node, it was part of the min cut. However, after some think time, I found that this still doesn't solve the last requirement, that the min cut must be in smallest lexicographic order.

SELF-CONTEMPLATION

As I stuck with this flood-fill idea, I came to the realization that Teacher Huang's proposal was correct after all, it will truly "weigh in" the edge count, to some degree. However, I knew that if this was to work, my original idea would need some tweaking, but I did not know where.

CONTEMPLATION II

Fellow students proposed several ideas, most using algorithms a la Tarjan and SCC which I did not know of, and some involving the most outrageously distant possibilities, such as doing DP on the graph and finding the min cut for all s-t pairs. One suggested that we just check in lexicographic order if removing an edge decreases the max flow by exactly the edge's weight. At the time my minuscule brain did not understand what this forbade; only when we worked through my original "USACO algorithm wrong" example did I understand why the decrease amount constraint was so important - if we arbitrarily removed edges, the total removed edge weight sum wouldn't equal the original max flow! Now, it must be the min cut since the MCMF theorem holds. As an example, in the "USACO algorithm wrong" graph removing an weight 1001 edge reduces the total flow from 2001 to 1001, not 1000, so in the end, the min cut would use an extra weight unit.

Attempt 3 (AC)

This method was fairly easy to implement, given I already had my attempt 1 code, as it only involved few edits. Then, there were the measly borderline cases, such as using LONG LONG instead of INT data type, printing on newlines instead of spaces, etc. At the end, I finally got AC.

LOOKING BACK

In hindsight, although indeed the USACO min cut explanation did not jack shit about lexicographic ordering, it did mention (in fine print and parentheses) that if we remove an edge that is part of the min cut, it should both decrease the max flow, and more precisely, it should decrease the max flow by exactly the edge's weight. So half of the problem is me skipping material I thought was "obvious" but actually wasn't in the long run.

USACO ANALYSIS

I really think USACO tried to hide there not-acknowledging lexicographic ordering, since even the solution code did not implement it, and a student had to point it out underneath. *facepalm* Furthermore, it did not use the original USACO min cut algorithm, but instead used the flood-fill algorithm. The student also pointed out that even with a fix to implement lexicographic ordering, this method will still not work for some test cases. *DOUBLE FACEPALM* Come on.......

A SUMMARY: OF CODING

- If an edge is part of min cut, removing it from the graph will decrease the graph's max flow by the edge weight.

A SUMMARY: OF METHODS AND PRINCIPLES

 - Even the most trivial statements may prove important.

 - Be open to all ideas.

/*

TASK: milk6

ID: qlstudi3

LANG: C++14

*/

#include <algorithm>

#include <fstream>

#include <queue>

#include <vector>

#include <cstring>

using namespace std;

ifstream cin("milk6.in");

ofstream cout("milk6.out");

struct qel {

long long flow;

vector<int> path;

const bool operator< (const qel other) const {

return flow < other.flow;

}

};

int N;

long long dijmat[35][35];

long long vist[35];

qel flow()

{

priority_queue<qel> pq;

memset(vist, 255, sizeof vist);

pq.push({0xFFFFFFFFFFFull, {1}});

vist[1] = 0xFFFFFFFFFFFull;

while(!pq.empty()) {

qel top = pq.top(); pq.pop();

//cout << "pull flow " << top.flow << "@" << top.path.back() << endl;

if(top.path.back() == N) return top;

for(int i=1; i<=N; i++)

if(dijmat[top.path.back()][i] != 0) {

//cout << i << endl;

qel next = top;

next.flow = min(top.flow, dijmat[top.path.back()][i]);

if(next.flow <= vist[i]) continue;

next.path.push_back(i);

vist[i] = next.flow;

pq.push(next);

}

}

return {0, {}};

}

long long flowmat[35][35];

long long maxflow() {

memcpy(dijmat, flowmat, sizeof dijmat);

long long totflow = 0;

while(1) {

qel f = flow();

if(f.flow == 0) return totflow;

totflow += f.flow;

int pnode = -1;

for(int i:f.path) {

if(pnode == -1) { pnode = i; continue; }

dijmat[pnode][i] -= f.flow;

dijmat[i][pnode] += f.flow;

pnode = i;

}

}

}

long long edgemat[35][35];

int M;

struct edge {

int s, e, id;

long long pr;

const bool operator< (const edge other) const {

if(pr != other.pr) return pr < other.pr;

else return id < other.id;

}

} edges[1005];

vector<int> mincut()

{

memcpy(flowmat, edgemat, sizeof flowmat);

long long maxf = maxflow();

vector<int> ans;

for(int i=0; i<M; i++)

{

flowmat[edges[i].s][edges[i].e]-=edges[i].pr;

long long nflow = maxflow();

if(maxf - nflow == edges[i].pr)

{

ans.push_back(edges[i].id);

maxf = nflow;

} else {

flowmat[edges[i].s][edges[i].e]+=edges[i].pr;

}

}

return ans;

}

int main()

{

cin >> N >> M;

for(int i=0; i<M; i++)

{

cin >> edges[i].s >> edges[i].e; long long weight; cin >> weight;

weight = (10000*weight+1);

edges[i].pr = weight;

edges[i].id = i+1;

edgemat[edges[i].s][edges[i].e] += weight;

}

memcpy(flowmat, edgemat, sizeof flowmat);

cout << maxflow()/10000 << " ";

vector<int> mc = mincut();

sort(mc.begin(), mc.end());

cout << mc.size() << endl;

for(int i:mc)

cout << i << endl;

}