Pagini recente » Cod sursa (job #2311381) | Cod sursa (job #2239224)
#include <bits/stdc++.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int NMAX = 205;
struct Edge {
int to, cap, flow, rev;
};
vector<Edge> g[NMAX];
int cap[NMAX][NMAX], n, m, rem[NMAX];
void addEdge(int i, int j) {
Edge a = {j, cap[i][j], 0, g[j].size()};
Edge b = {i, cap[j][i], 0, g[i].size()};
g[i].push_back(a);
g[j].push_back(b);
}
int dist[NMAX];
bool bfs() {
for(int i = 0; i <= m; i ++)
dist[i] = -1;
dist[0] = 0;
queue<int> q;
q.push(0);
while(q.size()) {
int from = q.front();
q.pop();
for(auto it : g[from]) {
if(dist[it.to] == -1 && it.flow < it.cap) {
dist[it.to] = 1 + dist[from];
q.push(it.to);
}
}
}
return (0 <= dist[m]);
}
int flow[NMAX][NMAX];
int dfs(int from, int deltaflow) {
if(from == m)
return deltaflow;
for(int &i = rem[from]; i < g[from].size(); i ++) {
Edge &e = g[from][i];
if(dist[e.to] == 1 + dist[from] && e.flow < e.cap) {
int addflow = dfs(e.to, min(deltaflow, e.cap - e.flow));
if(addflow > 0) {
Edge &rev = g[e.to][e.rev];
e.flow += addflow;
rev.flow -= addflow;
flow[from][e.to] += addflow;
// cout << from << " " << e.to << " " << flow[from][e.to] << endl;
flow[e.to][from] -= addflow;
//cout << from << " " << e.to << " " << flow[e.to][from] << endl;
return addflow;
}
}
}
return 0;
}
int dinic() {
int maxflow = 0;
while(bfs()) {
for(int i = 0; i <= m; i ++)
rem[i] = 0;
int aux = dfs(0, INT_MAX);
while(aux) {
maxflow += aux;
//cout << maxflow << endl;
aux = dfs(0, INT_MAX);
}
}
return maxflow;
}
int main() {
in >> n;
m = 2 * n + 1;
for(int i = 1; i <= n; i ++) {
int x, y;
in >> x >> y;
cap[0][i * 2 - 1] = x; /// gradul dr iesire
addEdge(0, i * 2 - 1);
cap[i * 2][m] = y; /// gradul de intrare
addEdge(i * 2, m);
}
for(int i = 1; i < m; i += 2)
for(int j = 2; j < m; j += 2)
if(j - i != 1)
cap[i][j] = 1;
for(int i = 1; i < m; i ++)
for(int j = i + 1; j < m; j ++)
if(cap[i][j] || cap[j][i])
addEdge(i, j);
int maxflow = dinic();
vector<pair<int, int> > sol;
for(int i = 1; i < m; i += 2)
for(int j = 2; j < m; j += 2)
if(flow[i][j] == cap[i][j] && j - i != 1)
sol.push_back({(i + 1) / 2, (j + 1) / 2});
out << sol.size() << "\n";
for(auto it : sol)
out << it.first << " " << it.second << "\n";
return 0;
}