Cod sursa(job #2613568)

Utilizator EmilianManescuManescu Emilian-Claudiu EmilianManescu Data 9 mai 2020 22:41:03
Problema Taramul Nicaieri Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;

const int kNmax = 101;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n, N, m;
  	int C[2 * kNmax + 2][2 * kNmax + 2];
  	int s, t;
  	vector<int> parent;
  	vector<bool> visited;

	void read_input() {
		ifstream fin("harta.in");
		fin >> n;
		s = 0; t = 2 * n + 1;
		N = 2 * n;
		memset(C, 0, sizeof C);
		for (int i = 1, x, y; i <= n; i++) {
			fin >> x >> y;
     		C[s][i] = x;
     		C[n + i][t] = y;
     		for (int j = n + 1; j <= 2 * n; j++) {
				if((j - i) != n) {
					C[i][j] = 1;
				}
			}
		}
		fin.close();
	}

	bool bfs() {
		queue<int> q;
		int u;
		q.push(s);
		visited[s] = true;
		fill(visited.begin(), visited.end(), false);
		//memset(&visited[0], false, sizeof(visited[0]) * visited.size());

		while(!q.empty()) {
			u = q.front(); q.pop();
			for (int v = 0; v <= t; v++) {
				if (visited[v] == false && C[u][v]) {
					visited[v] = true;
					parent[v] = u;
					q.push(v);
				}
			}
		}
		return visited[t];
	}

	int get_result() {
		int flow = 0, aux_flow;
		int current, prev;
		parent.resize(N + 2, -1);
		visited.resize(N + 2, false);
		bool result = false;

		while (true) {
			result = bfs();
			if (!result) {
				break;
			}
			aux_flow = (1 << 30);
			current = t;
			while (current != s) {
				prev = parent[current];
				aux_flow = min(aux_flow, C[prev][current]);
				current = prev;
			}

			current = t;
			while (current != s) {
				prev = parent[current];
				C[prev][current] -= aux_flow;
				C[current][prev] += aux_flow;
				current = prev;
			}

			flow += aux_flow;
		}
		return flow;
	}

	void print_output(int result) {
		ofstream fout("harta.out");
		fout << result << '\n';
		for (int i = 1; i <= n; i++) {
			for (int j = n + 1; j <= 2 * n; j++) {
				if ((j - i) != n && C[i][j] == 0) {
					fout << i << " " << j - n << endl;
				}
			}
		}
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}