USACO 4.2 The Perfect Stall – CPP solution

We need to match as much as values from the set N with the set M. We just create a graph where every element of N is connected to every possible to match element in M. Then we run a slightly modified DFS or as some people refer to it a modified flow alrorithm. It doesn’t really matter how we call it since the flow algorithms just find as much as possible paths from the source to the sink using either BFS, DFS or PFS (priority-first search or best-first search).

In other words we just check whether an element q from N can be matched with an element t of M. If q is possible to match with t but t is matched with another element z of the set N, we check whether that element z can be matched with another element in M. If it is possible, then we can for sure make such changes that q matches t since z can match another free element in M.

We do this for every element q in N.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m;
int g[201][201];
int marked[201];
int used[201];

int dfs(int k) {
    for (int i = 1; i<=m; ++i) {
        if(g[k][i]<=0) continue;
        used[i] = 1;
        if (marked[i]==-1 || dfs(marked[i])) {
            marked[i] = k;
            return 1;
        }
    }
    return 0;
}

int flow() {

    memset(marked,-1,sizeof(marked));

    int ans = 0;

    for (int i = 1; i <= n; ++i) {
        memset(used,0,sizeof(used));
        ans += dfs(i);
    }

    return ans;

}

int main() {
    FILE *in = fopen("stall4.in", "r");
    fscanf(in, "%d%d", &n,&m);
    for (int i = 1; i<= n; ++i) {
        int c;
        int k;
        fscanf(in, "%d", &c);
        for (int z = 0; z < c; ++z) {
            fscanf(in, "%d", &k);
            g[i][k] = 1;
        }
    }
    fclose(in);
    FILE * out = fopen("stall4.out", "w");

    fprintf(out, "%dn", flow());
    fclose(out);

    return 0;
}

USACO 4.2 – Drainage Ditches CPP Solution

The problem is standard. Just use some flow algorithm. The constraints are small. You do not have to use Dinic here.

#include <algorithm>
#include <cstdio>
using namespace std;

#define MAX 999999

int n,m;
int g[201][201] = {0};
int path[201];

int found, minFlow;

void clear() {
    for (int i = 1; i<= n; ++i) path[i] = -1;
    found = 0;
    minFlow = MAX;
}

void dfs(int k, int parent) {
    if (found) return;
    if (path[k] != -1) return;
    path[k] = parent;
    if (k == n) {
        found = 1;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (g[k][i]>0) {
            dfs(i, k);
        }
    }
}


int flow() {
    int ans = 0;

    while(1) {
        clear();
        dfs(1, 0);
        if (path[n] == -1) return ans;
        int v1 = path[n],v2 =n, tmp = MAX;
        while(1) {
            if (v1 < 1) break;
            tmp = min(g[v1][v2], tmp);
            v2 = v1;
            v1 = path[v1];
        }
        v1 = path[n], v2 = n;
        ans += tmp;
        while (1) {
            if (v1 < 1) break;
            g[v1][v2] -= tmp;
            g[v2][v1] += tmp;
            v2 = v1;
            v1 = path[v1];
        }
    }

    return ans;
}

int main() {
    FILE * in = fopen("ditch.in", "r");
    FILE * out = fopen("ditch.out", "w");
    fscanf(in ,"%d%d", &m,&n);
    int a,b,c;
    for (int i = 0; i < m; ++i) {
        fscanf(in, "%d%d%d",&a,&b,&c);
        g[a][b] += c;
    }
    fprintf(out, "%dn", flow());
    fclose(in);
    fclose(out);
    return 0;
}