Pagini recente » Cod sursa (job #1083861) | Cod sursa (job #2957163) | Cod sursa (job #1988703) | Cod sursa (job #1950709) | Cod sursa (job #1887522)
#include <cstdio>
#include <vector>
#include <cstring>
#define MAXN 202
#define INF 0x3f3f3f3f
using namespace std;
vector <int> G[MAXN];
int source, sink, n, maxflow, flow[MAXN][MAXN], capacity[MAXN][MAXN], dad[MAXN], q[MAXN];
bool seen[MAXN];
inline bool bfs()
{
int node, left, right, son, i;
memset(seen, 0, sizeof seen);
left = right = 0;
q[right++] = source;
seen[source] = 1;
while(left < right) {
node = q[left++];
if(node == sink) continue;
for(i=0; i<G[node].size(); ++i)
if(!seen[G[node][i]] && flow[node][G[node][i]] < capacity[node][G[node][i]]) {
son = G[node][i];
seen[son] = 1;
dad[son] = node;
q[right++] = son; } }
return seen[sink];
}
inline int pump()
{
int node, a = 0, minflow, i;
for(i=0; i<G[sink].size(); ++i)
if(seen[G[sink][i]] && flow[G[sink][i]][sink] < capacity[G[sink][i]][sink]) {
dad[sink] = G[sink][i];
minflow = INF;
for(node=sink; node!=source; node=dad[node])
minflow = min(minflow, capacity[dad[node]][node] - flow[dad[node]][node]);
if(minflow)
for(node=sink; node!=source; node=dad[node])
flow[dad[node]][node] += minflow, flow[node][dad[node]] -= minflow;
a += minflow;
}
return a;
}
int main()
{
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
int i, j, x, y;
scanf("%d", &n);
for(i=1; i<=n; ++i) {
scanf("%d%d", &x, &y);
G[0].push_back(i);
G[i].push_back(0);
capacity[0][i] = x;
G[2*n+1].push_back(i+n);
G[i+n].push_back(2*n+1);
capacity[i+n][2*n+1] = y; }
for(i=1; i<=n; ++i)
for(j=n+1; j<=2*n; ++j)
if(i+n != j) {
G[i].push_back(j);
G[j].push_back(i);
capacity[i][j] = 1; }
source = 0;
sink = 2*n+1;
while(bfs()) maxflow += pump();
printf("%d\n", maxflow);
for(i=1; i<=n; ++i)
for(j=n+1; j<=2*n; ++j)
if(flow[i][j])
printf("%d %d\n", i, j-n);
return 0;
}