Pagini recente » Cod sursa (job #2238177) | Cod sursa (job #1273817) | Cod sursa (job #1224127) | Cod sursa (job #2020838) | Cod sursa (job #3331838)
#include <fstream>
#include <queue>
#include <vector>
#define inf 1e9
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
int c[205][205],flow[205][205],dist[205],m,n;
vector<int>v[205];
queue<int>q;
bool bfs(int s,int d){
for(int i=0;i<=2*n+1;i++)
dist[i]=inf;
q.push(s);
dist[s]=1;
while(!q.empty()){
int nod=q.front();
q.pop();
for(auto i:v[nod])
if(dist[i]>dist[nod]+1&&flow[nod][i]<c[nod][i]){
dist[i]=dist[nod]+1;
q.push(i);
}
}
return dist[d]!=inf;
}
int dinic(int nod,int d,int val){
if(val==0)
return 0;
if(nod==d)
return val;
int total=0;
for(auto i:v[nod])
if(dist[i]==dist[nod]+1){
int add=dinic(i,d,min(c[nod][i]-flow[nod][i],val-total));
flow[nod][i]+=add;
flow[i][nod]-=add;
total+=add;
}
return total;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>c[0][i]>>c[i+n][2*n+1];
v[0].push_back(i);
v[i].push_back(0);
v[i+n].push_back(2*n+1);
v[2*n+1].push_back(i+n);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j){
v[i].push_back(j+n);
v[j+n].push_back(i);
c[i][j+n]=1;
}
while(bfs(0,2*n+1))
m+=dinic(0,2*n+1,inf);
cout<<m<<'\n';
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(flow[i][j+n]==1)
cout<<i<<" "<<j<<'\n';
return 0;
}