Pagini recente » Cod sursa (job #1367246) | Cod sursa (job #1226183) | Cod sursa (job #1366963) | Cod sursa (job #734196) | Cod sursa (job #282018)
Cod sursa(job #282018)
#include <cstdio>
#include <string>
#define N 256
int cap[N][N];
int n, in[101], out[101];
int t[N];
int source, sink;
void read()
{
freopen("harta.in","r",stdin);
scanf("%d\n", &n);
for(int i=1; i <= n; ++i) scanf("%d %d\n", &out[i], &in[i]);
source=0;
sink=2*n+1;
int i, j;
for(i=1; i <= n; ++i) cap[source][i]=out[i];
for(i=n+1; i < sink; ++i) cap[i][sink]=in[i-n];
for(i=1; i <= n; ++i)
for(j=n+1; j < sink; ++j)
if(i != j-n) cap[i][j]=1;
}
int bfs()
{
int Q[N], p=0, q=0,u,i;
bool use[N];
memset(use, 0, sizeof(use));
memset(t, -1, sizeof(t));
use[source]=1;
Q[0]=source;
while(p <= q)
{
u=Q[p++];
for(i=source; i <= sink; ++i)
if(!use[i])
if(cap[u][i] > 0)
{
Q[++q]=i;
t[i]=u;
use[i]=1;
}
}
if(t[sink] == -1) return 0;
return 1;
}
void solve()
{
int i, j;
int flow=0;
while(bfs())
{
for(i=n+1; i < sink; ++i)
if(t[i] && cap[i][sink])
{
--cap[i][sink];
++cap[sink][i];
for(j=i; j != source; j=t[j])
--cap[t[j]][j],
++cap[j][t[j]];
++flow;
}
}
freopen("harta.out","w",stdout);
printf("%d\n", flow);
for(i=1; i <= n; ++i)
for(j=n+1; j < sink; ++j)
if(i != j-n)
if(cap[i][j] == 0) printf("%d %d\n", i, j-n);
}
int main()
{
read();
solve();
return 0;
}