Pagini recente » Istoria paginii runda/oni-2009-x | Cod sursa (job #1649407) | Cod sursa (job #698695) | Cod sursa (job #1105219) | Cod sursa (job #1723889)
#include<cstdio>
#include<cstring>
#define MAXN 210
#define INF 100000000
using namespace std;
int capacity[MAXN][MAXN],flow[MAXN][MAXN],seen[MAXN],dad[MAXN],Queue[MAXN];
int source,sink;
int minimum(int a,int b){
if(a<b)
return a;
return b;
}
bool BFS(){
int left=1,right=1,i,node;
memset(seen,0,sizeof(seen));
Queue[left]=source;
seen[source]=1;
while(left<=right){
node=Queue[left];
left++;
if(node==sink)
continue;
for(i=1;i<=sink;i++)
if(seen[i]==0&&capacity[node][i]!=flow[node][i]){
seen[i]=1;
right++;
Queue[right]=i;
dad[i]=node;
}
}
if(seen[sink]==1)
return true;
return false;
}
int main(){
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
int n,i,j,k,add,node,edges=0;
scanf("%d",&n);
source=0;
sink=2*n+1;
for(i=1;i<=n;i++){
scanf("%d%d",&capacity[source][i],&capacity[i+n][sink]);
for(j=1;j<=n;j++)
if(i!=j)
capacity[i][j+n]=1;
}
while(BFS()==true)
for(i=0;i<=2*n;i++)
if(seen[i]==1&&capacity[i][sink]!=flow[i][sink]){
dad[sink]=i;
add=INF;
for(node=sink;node!=source;node=dad[node])
add=minimum(add,capacity[dad[node]][node]-flow[dad[node]][node]);
for(node=sink;node!=source;node=dad[node]){
flow[dad[node]][node]+=add;
flow[node][dad[node]]-=add;
}
edges+=add;
}
printf("%d\n",edges);
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;
}