## Solución al problema número MinCutBaahubali vs Bhallaladeva de HackerEarth - MinCutBaahubali vs Bhallaladeva.

Cualquier duda no dudes en contactar.

``````// Adjacency matrix implementation of Stoer-Wagner min cut algorithm.
//
// Running time:
//     O(|V|^3)
//
// INPUT:
//     - graph, constructed using AddEdge()
//
// OUTPUT:
//     - (min cut value, nodes in half of min cut)

#include <cmath>
#include <vector>
#include <iostream>
#include <queue>
#include <map>
#include <cstring>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

const int INF = 1000000000;

pair<int, VI> GetMinCut(VVI &weights) {
int N = weights.size();
VI used(N), cut, best_cut;
int best_weight = -1;

for (int phase = N-1; phase >= 0; phase--) {
VI w = weights[0];
int prev, last = 0;
for (int i = 0; i < phase; i++) {
prev = last;
last = -1;
for (int j = 1; j < N; j++)
if (!added[j] && (last == -1 || w[j] > w[last])) last = j;
if (i == phase-1) {
for (int j = 0; j < N; j++) weights[prev][j] += weights[last][j];
for (int j = 0; j < N; j++) weights[j][prev] = weights[prev][j];
used[last] = true;
cut.push_back(last);
if (best_weight == -1 || w[last] < best_weight) {
best_cut = cut;
best_weight = w[last];
}
} else {
for (int j = 0; j < N; j++)
w[j] += weights[last][j];
}
}
}
return make_pair(best_weight, best_cut);
}
struct Node {
int x, y, v;// x->y, v
int next;
} edge[105];
int e, head[105], dis[105], previ[105], record[105];
void addEdge(int x, int y, int v) {
edge[e].x = x, edge[e].y = y, edge[e].v = v;
edge[e].x = y, edge[e].y = x, edge[e].v = 0;
}
int maxflow(int s, int t) {
int flow = 0;
int i, x, y;
while(1) {
memset(dis, 0, sizeof(dis));
dis[s] =  0xffff; // oo
queue<int> Q;
Q.push(s);
while(!Q.empty()) {
x = Q.front();
Q.pop();
for(i = head[x]; i != -1; i = edge[i].next) {
y = edge[i].y;
if(dis[y] == 0 && edge[i].v > 0) {
previ[y] = x;
record[y] = i;
dis[y] = std::min(dis[x], edge[i].v);
Q.push(y);
}
}
if(dis[t])  break;
}
if(dis[t] == 0) break;
flow += dis[t];
for(x = t; x != s; x = previ[x]) {
int ri = record[x];
edge[ri].v -= dis[t];
edge[ri^1].v += dis[t];
}
}
return flow;
}

int main() {
e=0;
int N,aux=2;
cin >> N;
char S,T; cin>>S>>T;
map<char,int> M; M[S]=1; M[T]=N;
VVI weights(N, VI(N));
for (int i = 0; i < N; i++) {
char a, b; int c;
cin >> a >> b >> c;
if(M[a]==0) { M[a]=aux; aux++; }
if(M[b]==0) { M[b]=aux; aux++; }
weights[M[a]][M[b]] =  c;