Cod sursa(job #2204062)

Utilizator mihaela.balintMihaela Balint mihaela.balint Data 14 mai 2018 12:29:17
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

const int kNmax = 205;

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

 private:
	int n;
	int cities;
	vector<int> adj[kNmax];
	int C[kNmax][kNmax];
	int F[kNmax][kNmax];

	void read_input() {
		ifstream fin("harta.in");
		fin >> cities;
		n = 2*cities + 2;

		memset(C, 0, sizeof C);
		memset(C, 0, sizeof F);
		for (int i = 2, ins, outs; i <= cities + 1; i++) {
			fin >> outs >> ins;
			adj[1].push_back(i);
			adj[i].push_back(1);
			C[1][i] += outs;
			adj[cities + i].push_back(n);
			adj[n].push_back(cities + 1);
			C[cities + i][n] += ins;
		}
		for (int i = 2; i <= cities + 1; i++) 
			for (int j = 2; j <= cities + 1; j++) {
				if (i == j) continue;
				adj[i].push_back(cities + j);
				adj[cities + j].push_back(i);
				C[i][cities + j] = 1;
			}
	
		fin.close();
	}

	int get_result() {
		int flow = 0;
		while(1) {
			queue<int> q;
			vector<int> pred(n + 1, 0);
			vector<int> plus(n + 1, 0);
			q.push(1);
			plus[1] = 2147000000;
			while(!q.empty() && pred[n] == 0) {
				int u = q.front();
				q.pop();
				for (auto v : adj[u]) 
					if (!pred[v] && C[u][v] - F[u][v] > 0) {
						q.push(v);
						pred[v] = u;
						plus[v] = min(plus[u], C[u][v] - F[u][v]);
					}
			}

			if(!pred[n]) break;
			int added = plus[n];
			flow += added;
			for(int v = n; v != 1; v = pred[v]) {
				int u = pred[v];
				F[u][v] += added;
				F[v][u] -= added;
			}
		}
		
		return flow;
	}

	void print_output(int result) {
		ofstream fout("harta.out");
		fout << result << '\n';
		for (int i = 2; i <= cities + 1; i++) 
			for (int j = 2; j <= cities + 1; j++) 
				if (F[i][cities + j] == 1)
					fout << i - 1 << ' ' << j - 1 << '\n';
		fout.close();
	}
};

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