Pagini recente » Cod sursa (job #1654701) | Cod sursa (job #2762976) | Cod sursa (job #1621417) | Cod sursa (job #674707) | Cod sursa (job #2099055)
#include <bits/stdc++.h>
#define MAXN 100
#define INF 1000000000
#define BUF_SIZE 1 << 14
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
if(pbuf==BUF_SIZE){
fread(buf, BUF_SIZE, 1, fi);
pbuf=0;
}
return buf[pbuf++];
}
inline int nextnum(){
int a = 0;
char c = nextch();
while(!isdigit(c))
c = nextch();
while(isdigit(c)){
a = a * 10 + c - '0';
c = nextch();
}
return a;
}
int S, D;
std::vector <int> G[1 + 2 + 2 * MAXN];
int C[1 + 2 + 2 * MAXN][1 + 2 + 2 * MAXN];
int F[1 + 2 + 2 * MAXN][1 + 2 + 2 * MAXN];
int q[1 + 2 + 2 * MAXN];
int father[1 + 2 + 2 * MAXN];
int viz[1 + 2 + 2 * MAXN];
int bfs(){
memset(viz, 0, sizeof(viz));
q[0] = 1;
q[1] = S;
viz[S] = 1;
for(int i = 1; i <= q[0]; i++){
int node = q[i];
if(node != D)
for(int j = 0; j < G[node].size(); j++){
int vecin = G[node][j];
if(!viz[vecin] && C[node][vecin] != F[node][vecin]){
viz[vecin] = 1;
q[++q[0]] = vecin;
father[vecin] = node;
}
}
if(viz[D])
return viz[D];
}
return viz[D];
}
int main(){
fi = fopen("harta.in","r");
fo = fopen("harta.out","w");
int n = nextnum();
int sum = 0;
for(int i = 2; i <= n + 1; i++){
int x = nextnum(), y = nextnum();
sum += x + y;
G[1].push_back(i);
G[i].push_back(1);
C[1][i] = x;
G[i + n].push_back(2 * n + 2);
G[2 * n + 2].push_back(i + n);
C[i + n][2 * n + 2] = y;
for(int j = n + 2; j <= 2 * n + 1; j++)
if(j != i + n){
G[i].push_back(j);
G[j].push_back(i);
C[i][j] = 1;
}
}
S = 1;
D = 2 * n + 2;
while(bfs()){
for(int i = 0; i < G[D].size(); i++){
int node = G[D][i];
if(viz[node] && C[node][D] != F[node][D]){
father[D] = node;
int fmin = INF;
for(int node = D; node != S; node = father[node])
fmin = std::min(fmin, C[father[node]][node] - F[father[node]][node]);
if(fmin != 0)
for(int node = D; node != S; node = father[node]){
F[father[node]][node] += fmin;
F[node][father[node]] -= fmin;
}
}
}
}
fprintf(fo,"%d\n", sum / 2);
for(int i = 2; i <= n + 1; i++)
for(int j = n + 2; j <= 2 * n + 1; j++)
if(F[i][j] == C[i][j] && C[i][j])
fprintf(fo,"%d %d\n", i - 1, j - n - 1);
fclose(fi);
fclose(fo);
return 0;
}