Pagini recente » Cod sursa (job #1963135) | Cod sursa (job #2039404) | Cod sursa (job #291983) | Cod sursa (job #2565681) | Cod sursa (job #2958088)
#include <bits/stdc++.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
class Solution {
int n, m, source, sink;
vector<vector<int>> capacity, flow, adj;
vector<bool> viz;
vector<int> parent;
public:
Solution(int _n, vector<pair<int, int>> degs, int src, int sink);
bool bfs(int src);
void findMap();
};
bool Solution::bfs(int src) {
fill(viz.begin(), viz.end(), false);
fill(parent.begin(), parent.end(), -1);
queue<int> q;
q.push(src);
viz[src] = true;
int currNode;
while(!q.empty()) {
currNode = q.front();
q.pop();
for(auto nextNode : adj[currNode])
if(!viz[nextNode] && capacity[currNode][nextNode] - flow[currNode][nextNode] > 0) {
viz[nextNode] = true;
if(nextNode != sink) {
q.push(nextNode);
parent[nextNode] = currNode;
}
}
}
return viz[n];
}
void Solution::findMap() {
int maxFlow = 0;
while(bfs(source)) {
for(auto leaf : adj[sink]) {
if(capacity[leaf][sink] - flow[leaf][sink] <= 0 || !viz[leaf])
continue;
parent[sink] = leaf;
int minValOnPath = 110000;
for(int node = sink; parent[node] != -1; node = parent[node])
minValOnPath = min(minValOnPath, capacity[parent[node]][node] - flow[parent[node]][node]);
if(!minValOnPath)
continue;
maxFlow += minValOnPath;
for(int node = sink; parent[node] != -1; node = parent[node]) {
flow[parent[node]][node] += minValOnPath;
flow[node][parent[node]] -= minValOnPath;
}
}
}
cout << maxFlow << '\n';
for(int i = 1; i <= n; ++ i) {
for(int j = 1; j <= n; ++ j) {
if(i == j)
continue;
if(capacity[i][n + j] - flow[i][n + j] == 0)
cout << i << ' ' << j << '\n';
}
}
}
Solution::Solution(int _n, vector<pair<int, int>> degs, int src, int sink): n(_n), source(src), sink(sink) {
adj.resize(sink + 1);
viz.resize(sink + 1);
parent.resize(sink + 1);
capacity.resize(sink + 1, vector<int>(sink + 1, 0));
flow.resize(sink + 1, vector<int>(sink + 1, 0));
int degout, degin;
for(auto i = 0; i < degs.size(); ++ i) {
degout = degs[i].first; degin = degs[i].second;
adj[source].push_back(i + 1);
adj[i + 1].push_back(source);
capacity[source][i + 1] = degout;
adj[i + n + 1].push_back(sink);
adj[sink].push_back(i + n + 1);
capacity[i + n + 1][sink] = degin;
}
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j) {
if(i == j)
continue;
adj[i].push_back(j + n);
adj[j + n].push_back(i);
capacity[i][j + n] = 1;
}
}
int main() {
vector<pair<int, int>> deg;
int n, x, y;
in >> n;
for(int i = 0; i < n; ++ i) {
in >> x >> y;
deg.push_back({x, y});
}
Solution s(n, deg, 0, 2 * n + 1);
s.findMap();
return 0;
}