Pagini recente » Cod sursa (job #1871680) | Cod sursa (job #1027581)
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> G[205];
int C[205][205];
int F[205][205];
int N,P[205];
queue<int> Q;
bool bfs()
{
for(int i=1;i<=2*N+1;i++)
P[i]=-1;
Q.push(0);P[0]=0;
while(!Q.empty())
{
for(vector<int>::iterator it=G[Q.front()].begin();it!=G[Q.front()].end();it++)
if(P[*it]==-1 && F[Q.front()][*it]<C[Q.front()][*it])
{
P[*it]=Q.front();
Q.push(*it);
}
Q.pop();
}
if(P[2*N+1]!=-1)
return true;
return false;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&N);
for(int a,b,i=1;i<=N;i++)
{
scanf("%d%d",&a,&b);
G[0].push_back(i);
G[i].push_back(0);
G[N+i].push_back(2*N+1);
G[2*N+1].push_back(N+i);
C[0][i]=a;C[N+i][2*N+1]=b;
for(int j=1;j<=N;j++)
if(i!=j)
{
C[i][N+j]=1;
G[i].push_back(N+j);
G[N+j].push_back(i);
}
}
int total=0;
while(bfs())
{
int u=2*N+1,flux=1000000000;
while(u!=0)
{
flux=min(flux,C[P[u]][u]-F[P[u]][u]);
u=P[u];
}
u=2*N+1;
while(u!=0)
{
F[P[u]][u]+=flux;
F[u][P[u]]-=flux;
u=P[u];
}
total+=flux;
}
printf("%d\n",total);
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(F[i][N+j])
printf("%d %d\n",i,j);
return 0;
}