Pagini recente » Cod sursa (job #2077981) | Cod sursa (job #473334) | Profil niculae95 | Cod sursa (job #779563) | Cod sursa (job #3142912)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int INF = 1e9;
int n;
int din[105];
int dout[105];
vector<int> con[205];
int capacity[205][205];
int prec[205];
void add_edge(int x, int y, int w)
{
con[x].push_back(y);
con[y].push_back(x);
capacity[x][y]=w;
}
int bfs()
{
for(int i=1;i<=2*n+2;i++)
prec[i]=0;
prec[2*n+1]=-1;
deque<pair<int,int>> dq;
dq.push_back({2*n+1,INF});
while(!dq.empty())
{
int nod = dq.front().first;
int flow = dq.front().second;
dq.pop_front();
if(nod==2*n+2)
return flow;
for(auto adj:con[nod])
{
if(prec[adj]==0 && capacity[nod][adj]>0)
{
prec[adj]=nod;
dq.push_back({adj,min(flow,capacity[nod][adj])});
}
}
}
return 0;
}
void maxflow()
{
int flow=0;
while(1)
{
int x = bfs();
if(x==0)
break;
int cur=2*n+2;
while(cur!=2*n+1)
{
capacity[prec[cur]][cur]-=x;
capacity[cur][prec[cur]]+=x;
cur=prec[cur];
}
flow+=x;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j && capacity[i][j+n]==0)
fout<<i<<" "<<j<<"\n";
}
signed main()
{
fin>>n;
int tot=0;
for(int i=1;i<=n;i++)
{
fin>>dout[i]>>din[i];
add_edge(2*n+1,i,dout[i]);
add_edge(i+n,2*n+2,din[i]);
tot+=din[i];
}
fout<<tot<<"\n";
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
add_edge(i,j+n,1);
maxflow();
}