Cod sursa(job #2958587)

Utilizator Tudose_StefanTudose Alexandru Stefan Tudose_Stefan Data 27 decembrie 2022 00:07:46
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int cty[202][202], fl[202][202];
int tata[202];
vector <int> viz;
vector <vector <int>> adjL;
int n, nr1, nr2, i, j, flow, minn;

int BFS(){
	queue<int> q;
	q.push(0);
	viz.assign(n+n+2, 0);
	viz[0] = 1;
	while(!q.empty()){
		nr1 = q.front();
		q.pop();
		if(nr1 == n+n+1)
			break;
		for(auto &i : adjL[nr1]){
			if (!viz[i] && fl[nr1][i] != cty[nr1][i]){
				viz[i] = 1;
				tata[i] = nr1;
				q.push(i);
			}
		}
	}

	return viz[n];
}

int main()
{
    fin >> n;
    adjL.resize(n*2+2);
    for (i = 1; i <= n; ++i){
        fin >> nr1 >> nr2;
        cty[0][i] = nr1;
        cty[i+n][n+n+1] = nr2;
        adjL[0].push_back(i);
        adjL[i].push_back(0);
        adjL[n+n+1].push_back(i+n);
        adjL[i+n].push_back(n+n+1);
        for (j = 1; j <= n; ++j){
            if (i != j){
                cty[i][j+n] = 1;
                adjL[i].push_back(j+n);
                adjL[j+n].push_back(i);
                cty[j+n][i];
            }
        }
    }
    flow = 0;
  	while(BFS()){
  		for(auto &i:adjL[n+n+1]){
  			minn = INT_MAX;
  			tata[n+n+1] = i;
  			j = n + n + 1;
  			while(j > 0){
  				minn = min(minn, cty[tata[j]][j] - fl[tata[j]][j]);
  				j = tata[j];
  			}
  			for (j = n + n + 1; j> 0; j = tata[j]){
  				fl[tata[j]][j] += minn;
  				fl[j][tata[j]] -= minn;
  			}
  			flow += minn;
  		}
  	}
    fout << flow << '\n';
    for (i = 1; i <= n; ++i){
        for (auto k: adjL[i]){
            if (k != 0 && fl[i][k])
                fout << i << ' ' << k -n << '\n';
        }
    }
    return 0;
}