CodeArchive AllPairMinCut

All Pair Min Cut

A minimum cut algorithm without flow.

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

int data[256][256], dist[256], done[256], ans, best, ind, a, b, c, n, m, t, test = 1;

int main(){

 scanf("%d", &t);
 while(t-- && scanf("%d%d", &n, &m) == 2){
   memset(data, 0, sizeof(data));
   while(m-- && scanf("%d%d%d", &a, &b, &c) == 3)
     data[a - 1][b - 1] += c, data[b - 1][a - 1] += c;

   ans = 2000000000;
   while(n > 1){
     memset(dist, 0, sizeof(dist));
     memset(done, 0, sizeof(done));
     for(int i = 0; i < n; i++){
       best = ind = -1;
       for(int j = 0; j < n; j++)
         if(!done[j] && dist[j] > best)
           best = dist[j], ind = j;
       if(i + 2 == n) a = ind;
       if(i + 1 == n) b = ind, ans <?= best;
       done[ind] = 1;
       for(int j = 0; j < n; j++) dist[j] += data[ind][j];
     }

     if(a > b) a ^= b ^= a ^= b;
     for(int i = 0; i < n; i++) data[a][i] += data[b][i], data[i][a] += data[i][b];
     for(int i = 0; i < n; i++) data[b][i] = data[n - 1][i], data[i][b] = data[i][n - 1];
     n--;
   }

   printf("Case #%d: %d\n", test++, ans);
 }

 return 0;
}

-- Main.MatthewChan - 27 Jan 2006

All Pair Min Cut with Cut Recovery

// ************************** ALL-PAIR MIN CUT + CUT RECOVERY *********************************
// Inner loop grows most tightly bound cluster. Last added node is mincut candidate.
// Outer loop merges the two last nodes merged in inner loop
int n, m, u, v, d;   // n = number of nodes
int graph[150][150]; // adjacency matrix
int dist[150]; bool done[150]; // inner loop: dist = dist to cluster. done = is in cluster
bool merged[150]; int uf[150]; // outer loop: merged = merged sometime, uf = who are you merged with
int bestNum, bestSet[150], minCut; // result. # of nodes in a cut, nodes in the cut, and minimum cut.
int FIND(int k) { return (uf[uf[k]] == uf[k]) ? uf[k] : (uf[k] = FIND(uf[k])); }
void UNION(int a, int b) { uf[FIND(b)] = FIND(a); }
int main() {
  int nc; scanf("%d", &nc);
  for(int cs = 1; cs <= nc; cs++) {
    memset(graph, 0, sizeof(graph));
    memset(merged, 0, sizeof(merged));
    minCut = INT_MAX;
    // TO DO: read in graph: n = num of nodes, graph[][] is dist, no edge is 0
    int nleft = n; // nodes left (decreases when nodes are merged)
    while(nleft > 1) { // outer loop
      memset(dist, 0, sizeof(dist));
      memset(done, 0, sizeof(done));
      int node, bestDist;
      for(int i = 0; i < nleft; i++) { // inner loop: grow cluster
        node = bestDist = -1;          // find next tightly bound thing
        for(int j = 0; j < n; j++) if(!merged[j] && !done[j] && (dist[j] > bestDist)) {
          node = j; bestDist = dist[j];
        }
        done[node] = true; // add to cluster, update distances
        if (i == nleft-2) u = node;
        if (i == nleft-1) v = node;
        for(int k = 0; k < n; k++) if(!merged[k] && !done[k])
          dist[k] += graph[node][k];
      }
      if (bestDist < minCut) { // see if min cut is better and record it
        bestNum = 0;
        int parent = FIND(v);
        for(int i = 0; i < n; i++) if (FIND(i) == parent)
            bestSet[bestNum++] = i;
        minCut = bestDist;
      }
      for(int k = 0; k < n; k++) if(!merged[k]) { // merge u and v
        graph[u][k] += graph[v][k];
        graph[k][u] += graph[v][k];
        merged[v] = true;
        UNION(u, v);
      }
      nleft--;
    }
    printf("Case #%d: %d\n", cs, minCut);
  }
  return 0;
}

-- Main.SapphireJay - 04 Apr 2006