[Toph] Ghosh vs Datta

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Ghosh vs Datta
Source            : Toph
Category          : Graph Theory, Maximum Flow
Algorithm         : Dinic Algorithm
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define inf                 1e6  
#define pii                 pair <int, int>  
#define ll                  long long  
  
static const int maxn = 100 + 5;  
  
struct Dinic  
{  
      int N;  
      vector <int> graph[maxn];  
      ll cap[maxn][maxn], flow[maxn][maxn];  
      int level[maxn], ptr[maxn];  
      Dinic(int n)  
            : N(n)  
            {  
                  for (int i = 0; i < maxn; i++)  
                  {  
                        graph[i].clear();  
                        level[i] = ptr[i] = 0;  
                        for (int j = 0; j < maxn; j++) cap[i][j] = flow[i][j] = 0;  
                  }  
            }  
  
      void addEdge(int u, int v, ll w)  
      {  
            cap[u][v] = w;  
            flow[u][v] = 0;  
            graph[u].push_back(v);  
            graph[v].push_back(u);  
      }  
      void updateEdge(int u, int v, ll w)  
      {  
            cap[u][v] = w;  
            flow[u][v] = 0;  
      }  
      bool bfs(int src, int sink)  
      {  
            memset(level, -1, sizeof level);  
            queue <int> PQ;  
            PQ.emplace(src);  
            level[src] = 0;  
            while (!PQ.empty())  
            {  
                  int u = PQ.front(); PQ.pop();  
                  for (int v : graph[u])  
                  {  
                        if (level[v] != -1 || flow[u][v] >= cap[u][v]) continue;  
                        level[v] = level[u] + 1;  
                        PQ.emplace(v);  
                  }  
            }  
            return level[sink] != -1;  
      }  
      ll dfs(int u, ll minCap, int sink)  
      {  
            if (u == sink) return minCap;  
            for (int &i = ptr[u]; i < int(graph[u].size()); i++)  
            {  
                  int v = graph[u][i];  
                  if (level[v] == level[u] + 1 && flow[u][v] < cap[u][v])  
                  {  
                        ll minFlow = dfs(v, min(minCap, cap[u][v] - flow[u][v]), sink);  
                        if (minFlow > 0)  
                        {  
                              flow[u][v] += minFlow;  
                              flow[v][u] -= minFlow;  
                              return minFlow;  
                        }  
                  }  
            }  
            return 0;  
      }  
      ll dinic(int src, int sink)  
      {  
            ll maxFlow = 0;  
            while (bfs(src, sink))  
            {  
                  memset(ptr, 0, sizeof ptr);  
                  while (ll bottleneck = dfs(src, inf, sink))  
                        maxFlow += bottleneck;  
            }  
            return maxFlow;  
      }  
  
};  
  
ll init_cap[maxn][maxn];  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      freopen("in.txt", "r", stdin);  
  
      int tnode, tedge;  
      cin >> tnode >> tedge;  
  
      Dinic PMG(tnode);  
      Dinic TNT(tnode);  
  
      for (int e = 1; e <= tedge; e++)  
      {  
            int u, v;  
            ll w;  
            cin >> u >> v >> w;  
            ++u, ++v;  
            init_cap[u][v] = w;  
            PMG.addEdge(u, v, w);  
            TNT.addEdge(u, v, w);  
      }  
      int q;  
      cin >> q;  
      vector <pii> queries(q);  
      for (pii &x : queries)  
      {  
            cin >> x.first >> x.second;  
            ++x.first, ++x.second;  
            PMG.updateEdge(x.first, x.second, 0);  
            TNT.updateEdge(x.first, x.second, 0);  
      }  
      int pmg = 1;  
      int tnt = tnode;  
      ll pmg_tnt = 0, tnt_pmg = 0;  
      vector <string> ans(q);  
      for (int i = q - 1; i >= 0; i--)  
      {  
            pmg_tnt += PMG.dinic(pmg, tnt);  
            tnt_pmg += TNT.dinic(tnt, pmg);  
            if (pmg_tnt > tnt_pmg) ans[i] = "PMG";  
            else if (tnt_pmg > pmg_tnt) ans[i] = "TNT";  
            else if (tnt_pmg == 0 && tnt_pmg == 0) ans[i] = "Datta wins";  
            else if (tnt_pmg > 0 && tnt_pmg == pmg_tnt) ans[i] = "Ghosh wins";  
            int u = queries[i].first;  
            int v = queries[i].second;  
            PMG.updateEdge(u, v, init_cap[u][v]);  
            TNT.updateEdge(u, v, init_cap[u][v]);  
      }  
      for (int i = 0; i < q; i++) cout << ans[i] << '\n';  
}