Pagini recente » Cod sursa (job #76106) | Istoria paginii runda/16_februarie_simulare_oji_2024_clasa_9/clasament | Cod sursa (job #2418216) | Cod sursa (job #1252449) | Cod sursa (job #218975)
Cod sursa(job #218975)
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
#define pb push_back
#define lg 305
int n, i, j, prd[lg], c[lg][lg], t[lg][2];
vector<int> v[lg];
int find(){
int x, i;
bool fst[lg] = {0};
memset(prd, 0xff, sizeof(prd));
queue<int> q;
q.push(0), fst[0] = 1;
while (!q.empty()){
x = q.front(), q.pop();
for (i = 0; i < (int)v[x].size(); i ++)
if (!fst[v[x][i]] && c[x][v[x][i]] > 0){
fst[v[x][i]] = 1;
prd[v[x][i]] = x;
q.push(v[x][i]);
}
}
if (!fst[2*n+1])
return 0;
int mn = 0x3f3f3f3f;
for (x = 2*n+1; prd[x] != -1; x = prd[x])
mn = min(mn, c[prd[x]][x]);
for (x = 2*n+1; prd[x] != -1; x = prd[x]){
c[prd[x]][x] -= mn;
c[x][prd[x]] += mn;
}
return mn;
}
int flux(){
int x, rsp = 0;
do{
x = find();
rsp += x;
}
while (x > 0);
return rsp;
}
int main()
{
freopen("harta.in", "rt", stdin);
freopen("harta.out", "wt", stdout);
scanf("%d", &n);
for (i = 1; i <= n; i ++)
scanf("%d%d", &t[i][0], &t[i][1]);
for (i = 1; i <= n; i ++){
v[0].pb(i), v[i].pb(0), c[0][i] = t[i][0];
v[i+n].pb(2*n+1), v[2*n+1].pb(i+n), c[i+n][2*n+1] = t[i][1];
for (j = 1; j <= n; j ++)
if (i != j)
v[i].pb(n+j), v[n+j].pb(i), c[i][n+j] = 1;
}
printf("%d\n", flux());
for (i = 1; i <= n; i ++)
for (j = 1; j <= n; j ++)
if (!c[i][n+j] && i != j)
printf("%d %d\n", i, j);
return 0;
}