Pagini recente » Cod sursa (job #1155681) | Cod sursa (job #1607617) | Cod sursa (job #1124375) | Cod sursa (job #2556150) | Cod sursa (job #2960199)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
#define INF 9999999
vector<vector<int>>adj;
int capacity[202][202];
int tata[202];
int n;
int bfs(){
queue<pair<int,int>> q;
for(int i=0;i<=2*n+1;i++){
tata[i]=-1;
}
q.push({0,INF});
tata[0]=-2;
while(!q.empty()){
int u=q.front().first;
int flow=q.front().second;
q.pop();
for(auto v:adj[u]){
if(tata[v]==-1 && capacity[u][v]>0){
tata[v]=u;
int new_flow=min(flow,capacity[u][v]);
if(v==2*n+1)
return new_flow;
q.push({v,new_flow});
}
}
}
return 0;
}
int main() {
int x,y,i,j,flow,maxflow=0;
ifstream cin("harta.in");
ofstream cout("harta.out");
cin>>n;
adj.resize(2*n+2);
for(i=1;i<=n;i++){
cin>>x>>y;
adj[0].push_back(i);
adj[i].push_back(0);
capacity[0][i]=x;
capacity[n+i][2*n+1]=y;
adj[n+i].push_back(2*n+1);
adj[2*n+1].push_back(n+i);
for(j=n+1;j<=2*n;j++){
if(j-i==n)
continue;
capacity[i][j]=1;
adj[i].push_back(j);
adj[j].push_back(i);
}
}
while(flow=bfs()){
maxflow+=flow;
int cur=2*n+1;
while(cur!=0){
int prev=tata[cur];
capacity[cur][prev]+=flow;
capacity[prev][cur]-=flow;
cur=prev;
}
}
cout<<maxflow<<'\n';
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(capacity[j][i]==1){
cout<<i<<" "<<j-n<<'\n';
}
cin.close();
cout.close();
}