Dominoes Arrangement and Domino

Hi, surfing on BRSPOJ again, I've found a problem similar to another one that I already solved in Aizu Online Judge, they are these two: LinkAOJ and LinkSPOJ.

For the AOJ one, the input is a little different, but in it's essence, it's the same, given 'N' pieces of domino blocks   determine if it's possible to use all the pieces to form an whole valid sequence Dominoes. I've found 2 solutions, one using backtrack which runs in O(M + 2^N) with 'M' being the maximum number of values on a side of a piece and 'N' the total number of pieces.

This solution is good, but it's enough to pass through the tough system test of BRSPOJ, so I've turned to a graph solution, which is better, running only with a simple Depth-First-Search plus 2 iterations over the 'M', which runs in O(|V| + |E| + 2*M): These are the both solutions:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int a, b, i, j, k, n, ok, teste = 1, mem[7][7];

void rec(int now, int deep) {
    if(deep == n) {
        ok = 1;
        return;
    }
    for(j = 0; j &lt; = 6; j++) {
        int i = j;
        if(mem[now][i]&gt; 0) {
            mem[now][i]--;
            mem[i][now]--;
            rec(i, deep + 1);
            if(ok == 1) return;
            mem[now][i]++;
            mem[i][now]++;
        }
    }
}

int main(void) {
    while(scanf("%d", &amp; n) &amp; &amp; n != 0) {
        memset(mem, 0, sizeof(mem));
        ok = 0;
        for(i = 0; i &lt; n; i++) {
            scanf("%d%d", &amp; a, &amp; b);
            mem[a][b] += 1;
            mem[b][a] += 1;
        }
        for(k = 0; k &lt; = 6; k++) {
            rec(k, 0);
            if(ok == 1) break;
        }
        printf("Teste %d\n%s\n\n", teste++, ok == 1 ? "sim" : "nao");
    }
    return 0;
}

and

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int a, b, n, ok, teste = 1, mem[7][7], vis[7], ct[7];

void dfs(int x) {
    vis[x] = 1;
    for(int j = 0; j <= 6; j++) {
        if(vis[j] == 0 && mem[x][j] == 1) dfs(j);
    }
}

int main(void) {
    while(scanf("%d", &n) && n != 0) {
        memset(mem, 0, sizeof(mem));
        memset(vis, 0, sizeof(vis));
        memset(ct, 0, sizeof(ct));
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &a, &b);
            ct[a] += 1;
            ct[b] += 1;
            mem[a][b] = 1;
            mem[b][a] = 1;
        }
        for(int i = 0; i <= 6; i++) {
            if(ct[i] > 0) {
                dfs(i);
                break;
            }
        }
        ok = 1;
        for(int i = 0; i <= 6; i++) {
            if(ct[i] > 0 && !vis[i]) {
                ok = 0;
            }
        }
        int o = 0;
        for(int i = 0; i <= 6; i++) {
            if(ct[i] % 2 == 1) o++;
        }
        printf("Teste %d\n%s\n\n", teste++, ok == 1 && (o == 0 || o == 2) ? "sim" : "nao");
    }
    return 0;
}

Maximum-Flow

Hi, I've just implemented in C++ and good and clean Edmonds-Karp Maximum-Flow implementation, hope it would be useful to you too

#include <iostream>
#include <vector>

using namespace std;

vector graph[MAXN];
int capacity[MAXN][MAXN];

int max_flow(int source, int sink) {
    int residual[MAXN][MAXN];
    memset(residual, 0, sizeof(residual));
    while(1) {
        int prev[MAXN];
        memset(prev, -1, sizeof(prev));
        int actual[MAXN];
        memset(actual, 0, sizeof(actual));
        prev[source] = source;
        actual[source] = INF;
        queue q;
        q.push(source);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i = 0; i < graph[u].size(); i++) {
                int v = graph[u][i];
                if(capacity[u][v] - residual[u][v] > 0 && prev[v] == -1) {
                    prev[v] = u;
                    actual[v] = min(actual[u], capacity[u][v] - residual[u][v]);
                    if(v != sink) {
                        q.push(v);
                    } else {
                        while(prev[v] != v) {
                            u = prev[v];
                            residual[u][v] += actual[sink];
                            residual[v][u] -= actual[sink];
                            v = u;
                        }
                        goto end;
                    }
                }
            }
        }
        end:;
        if(prev[sink] == -1) {
            int sum = 0;
            for(int i = 0; i < MAXN; i++) {
                sum += residual[source][i];
            }
            return sum;
        }
    }
}

Minimum Cut Problem

Hello, working more on BRSPOJ problems (ACM/ICPC Regionals will be held next month) I found a different graph problem Link, the problems asks to find the minimum cut of a graph, my first and naive idea was just sort the edges and remove them by their lesser weights till disconnect some vertex from the graph. The idea was totally wrong, then I started to look for similar problems and solutions over the internet and figured out that it was a simple Minimum Cut problem, and some of their best solutions were the Stoer-Wagner algorithm which works in O(n^3):
Credits goes to Link

 
  #include <iostream>   
  #include <vector>   
  #include <algorithm>   
  #include <queue>   
  #include <stdio.h>   
  #include <stdlib.h>   
  #include <string.h>   
  using namespace std;   
  const int INF = 1000000000;   
  int test, n, m, a, b, c, ans, cont, graph[110][110];   
  int globalMinCut(int n) {   
   bool a[n];   
   int v[n];   
   int w[n];   
   for(int i = 0; i < n; i++) v[i] = i;   
   int best = INF;   
   while(n > 1) {   
    int maxj = 1;   
    a[v[0]] = true;   
    for(int i = 1; i < n; ++i) {   
     a[v[i]] = false;   
     w[i] = graph[v[0]][v[i]];   
     if(w[i] > w[maxj]) {   
      maxj = i;   
     }   
    }   
    int prev= 0 ,buf = n;   
    while(--buf) {   
     a[v[maxj]]=true;   
     if(buf == 1) {   
      best = min(best, w[maxj]);   
      for(int k = 0; k < n; k++) {   
       graph[v[k]][v[prev]]= (graph[v[prev]][v[k]] += graph[v[maxj]][v[k]]);   
      }   
      v[maxj] = v[--n];   
     }   
     prev = maxj;   
     maxj = -1;   
     for(int j = 1; j < n; ++j) {   
      if(!a[v[j]]) {   
       w[j] += graph[v[prev]][v[j]];   
       if(maxj < 0 || w[j] > w[maxj]) {   
        maxj=j;   
       }   
      }   
     }   
    }   
   }   
   return best;   
  }   
  int main(void) {   
   scanf("%d", &test);   
   for( ; test-- > 0; ) {   
    scanf("%d%d", &n, &m);   
    memset(graph, 0, sizeof(graph));   
    for(int i = 0; i < m; i++) {   
     scanf("%d%d%d", &a, &b, &c);   
     a -= 1;   
     b -= 1;   
     graph[a][b] = graph[b][a] = c;   
    }   
    printf("%d\n", globalMinCut(n));   
   }   
   return 0;   
  }