Pagini recente » Cod sursa (job #2438124) | Cod sursa (job #1573739) | Cod sursa (job #1185493) | Cod sursa (job #1352417) | Cod sursa (job #1754003)
#include <bits/stdc++.h>
#define maxN 205
#define INF (1<<30)
using namespace std;
queue<int>Que;
bool seen[maxN];
int t[maxN],nod;
int n,i,j,x,y,maxflow,addflow;
int cap[maxN][maxN],flow[maxN][maxN];
bool bfs()
{
while(!Que.empty())
Que.pop();
memset(seen,false,sizeof(seen));
Que.push(0);
seen[0]=true;
while(!Que.empty())
{
int node=Que.front();
Que.pop();
for(i=1;i<=2*n+1;i++)
{
if(cap[node][i]==flow[node][i] || seen[i])
continue;
seen[i]=true;
Que.push(i);
t[i]=node;
if(i == 2*n+1)
return true;
}
}
return false;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&cap[0][i],&cap[i+n][2*n+1]);
for(j=1;j<=n;j++)
if(i!=j)
cap[i][j+n]=1;
}
while(bfs())
{
addflow=INF;
for(nod=2*n+1;nod;nod=t[nod])
if(addflow>cap[t[nod]][nod]-flow[t[nod]][nod])
addflow=cap[t[nod]][nod]-flow[t[nod]][nod];
for(nod=2*n+1;nod;nod=t[nod])
flow[t[nod]][nod]+=addflow,
flow[nod][t[nod]]-=addflow;
maxflow+=addflow;
}
printf("%d\n",maxflow);
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(flow[i][j]==1)
printf("%d %d\n",i,j-n);
return 0;
}