USACO MAR09 Problem 'damage2' Analysis

by Jaehyun Park

We need to compute the minimum number of pastures that should be destroyed to disconnect the barn from every other given pasture. One intuitive answer is a maximum flow algorithm, since the max-flow of a graph is equal to the min-cut of it. But there is a problem; we cannot destroy cowpaths (edges), but only pastures (nodes).

This type of min-cut problem can be done by splitting each node into two, namely an upper node and a lower node. The network graph is constructed as the following:

• Each node is split into an upper node and a lower node, and there is an edge going from the upper node to the lower node with capacity one.
• For every undirected edge (u, v) in the original graph, make two directed edges (L_u, U_v), (L_v, U_u) with an infinite capacity, where L_i means the lower node of i and U_i is the upper node of i. In this problem, edges with capacity one are enough, since no more than one unit of flow can enter any lower node (except for the source which will be described below, but it doesn't matter because the barn is not directly connected to any pastures that cows reported).

Drawing the network will give more intuition (particularly, if you can draw it with two layers).

The source of the network is the lower node of the barn (node #1). For the sink, we make an imaginary sink connected to every upper node of the reported pastures. Now the graph is completely set. A max-flow algorithm will give the number of nodes which should be destroyed, as well as the indices of them.

The Korean version of the analysis is here.

//damage2 by Jaehyun Park

#include <stdio.h>
#include <memory.h>
#define PROBNAME "damage2"

#define UPPER(x) (((x)<<1)-1)
#define LOWER(x) ((x)<<1)
#define SOURCE (LOWER(1))
#define MAXN 3000
#define MAXM 20000
#define MAXNODE (MAXN<<1)
#define MAXEDGE ((MAXN+(MAXM<<1))<<1)

struct edge {
	int endpoint, next_edge, back_edge;
	bool avail;
};

FILE *ifp=fopen(PROBNAME".in", "r");
FILE *ofp=fopen(PROBNAME".out", "w");

int P, C, N;
int start_pointer[MAXNODE+1];
edge e[MAXEDGE+1];
int edge_count;

bool sink[MAXNODE+1];
bool visited[MAXNODE+1];

bool Find_Path (int x) {
    if(sink[x]) return true;
    visited[x]=true;
    int k;
    for(k=start_pointer[x];k;k=e[k].next_edge) {
        if (visited[e[k].endpoint] || !e[k].avail) continue;
        if (Find_Path(e[k].endpoint)) {
            e[k].avail=false; e[e[k].back_edge].avail=true;
            return true;
        }
    }
    return false;
}

int Max_Flow() {
    int flow;
    for(flow=0;;flow++) {
        memset(visited, false, sizeof(visited));
        if(!Find_Path(SOURCE)) break;
    }
    return flow;
}

void Make_Edge(int a, int b) {
    e[++edge_count].endpoint = b;
    e[edge_count].next_edge = start_pointer[a];
    e[edge_count].avail = true;
    e[edge_count].back_edge = edge_count+1;
    start_pointer[a] = edge_count;
    
    e[++edge_count].endpoint = a;
    e[edge_count].next_edge = start_pointer[b];
    e[edge_count].avail = false;
     e[edge_count].back_edge=edge_count-1;
    start_pointer[b]=edge_count;
}

void INPUT() {
    int i;
    int a, b;
    int report;
    fscanf (ifp, "%d%d%d", &P, &C, &N);
    for (i = 1; i <= P; i++) 
        Make_Edge(UPPER(i), LOWER(i));
    for(i = 1; i <= C; i++) {
        fscanf (ifp, "%d%d", &a, &b);
        Make_Edge (LOWER(a), UPPER(b));
        Make_Edge (LOWER(b), UPPER(a));
    }
    for(i=1;i<=N;i++) {
        fscanf (ifp, "%d", &report);
        sink[UPPER(report)]=true;
    }
}

void OUTPUT () {
    fprintf (ofp, "%d\n", Max_Flow());
}

void CLOSE_FILES() {
    fclose(ifp);
    fclose(ofp);
}

int main() {
    INPUT ();
    OUTPUT ();
    CLOSE_FILES ();
    return 0;
}