Pagini recente » Monitorul de evaluare | Statistici Ma Arunc de la Geam (maaruncdelageam) | Istoria paginii utilizator/alesimon.16 | Monitorul de evaluare | Cod sursa (job #2100087)
#include <bits/stdc++.h>
using namespace std;
const int INF = (int) 1e9;
const int MAXN = 301;
vector <int> g[MAXN + 1];
int cap[MAXN + 1][MAXN + 1];
int flx[MAXN + 1][MAXN + 1];
inline void addEdge(int x, int y, int c) {
cap[x][y] = c;
g[x].push_back(y);
g[y].push_back(x);
}
int from[MAXN + 1], q[MAXN + 1];
bool viz[MAXN + 1];
inline bool bfs(int s, int d) {
memset(viz, 0, sizeof(viz));
int b = 0, e = 0;
q[e++] = s;
viz[s] = 1;
while(b < e) {
int nod = q[b];
for(auto it : g[nod]) {
if(cap[nod][it] > flx[nod][it] && viz[it] == 0) {
q[e++] = it;
from[it] = nod;
viz[it] = 1;
}
}
b++;
}
return viz[d];
}
vector < pair <int, int> > sol;
int main() {
ifstream cin("harta.in");
ofstream cout("harta.out");
int i, j, n, x, y;
ios::sync_with_stdio(false);
cin >> n;
int s = 0, d = 3 * n + 1;
for(i = 1; i <= n; i++) {
cin >> x >> y;
addEdge(s, i, INF);
addEdge(i, i + n, x);
for(j = 1; j <= n; j++) {
if(j != i)
addEdge(i + n, j + 2 * n, 1);
}
addEdge(i + 2 * n, d, y);
}
while(bfs(s, d)) {
int nod = d;
int mn = INF;
while(nod != s) {
mn = min(mn, cap[from[nod]][nod] - flx[from[nod]][nod]);
nod = from[nod];
}
nod = d;
while(nod != s) {
flx[from[nod]][nod] += mn;
flx[nod][from[nod]] -= mn;
nod = from[nod];
}
}
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
int val = flx[i + n][j + 2 * n];
while(val > 0) {
val--;
sol.push_back({i, j});
}
}
}
cout << sol.size() << "\n";
for(auto it : sol) {
cout << it.first << " " << it.second << "\n";
}
return 0;
}