Cod sursa(job #2456358)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 14 septembrie 2019 11:13:48
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>



using namespace std;

const int N=200+7;

struct dumbFlow {
  int n;
  int cap[N][N];
  int par[N];
  vector <int> g[N];
  bool vis[N];

  void AddEdge(int a, int b, int c) {
    cap[a][b] += c;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  bool BFS() {
    for (int i = 1; i <= n; i++) {
      vis[i] = 0;
    }
    queue <int> Q;
    Q.push(1);

    while (!Q.empty()) {
      int nod = Q.front();
      Q.pop();

      if (nod == n) {
        continue;
      }

      for (auto &nou : g[nod]) {
        if (!vis[nou] && cap[nod][nou]) {
          vis[nou] = 1;
          par[nou] = nod;
          Q.push(nou);
        }
      }

    }
    return vis[n];
  }

  int maxFlow() {
    int flow = 0;

    while (BFS()) {

      for (auto &nod : g[n]) {
        if (vis[nod]) {
          int curNode = nod, curMin = cap[nod][n];
          while (curMin > 0 && curNode != 1) {
            curMin = min(curMin, cap[par[curNode]][curNode]);
            curNode = par[curNode];
          }
          if (curMin > 0) {
            flow += curMin;
            int curNode = nod;
            while (curNode != 1) {
              cap[par[curNode]][curNode] -= curMin;
              cap[curNode][par[curNode]] += curMin;
              curNode = par[curNode];
            }
            cap[nod][n] -= curMin;
            cap[n][nod] += curMin;
          }
        }
      }
    }

    return flow;
  }

};

dumbFlow fl;
int n;

int main()
{
        freopen("harta.in","r",stdin);
        freopen("harta.out","w",stdout);

        cin>>n;
        fl.n=2*n+2;
        for(int i=1;i<=n;i++)
        {
                int x,y;
                cin>>x>>y;
                fl.AddEdge(1,i+1,x);
                fl.AddEdge(i+n+1,2*n+2,y);
        }

        for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                        if(i!=j)
                                fl.AddEdge(i+1,j+n+1,1);

        cout<<fl.maxFlow()<<"\n";
        for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                        if(i!=j && fl.cap[i+1][j+n+1]==0)
                                cout<<i<<" "<<j<<"\n";

        return 0;
}