Pagini recente » Cod sursa (job #3152124) | Cod sursa (job #2872045) | Cod sursa (job #2634640) | Cod sursa (job #418515) | Cod sursa (job #3191372)
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n, src, dst;
vector<int>G[2*N];
vector<bool>viz;
int capacity[2*N][2*N],flow[2*N][2*N],t[2*N];
void bfs()
{
viz.assign(dst + 1, false);
queue<int> q;
q.push(src);
viz[src]=true;
t[src]=0;
while(!q.empty())
{
int current=q.front();
q.pop();
if(current == dst)
continue;
for(int next:G[current])
{
if(!viz[next] && capacity[current][next]!=flow[current][next])
{
viz[next]=true;
t[next]=current;
q.push(next);
}
}
}
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
src=0;
dst=2*n+1;
int totalMuchii = 0;
for(int i=1;i<=n;i++)
{
int out,in;
scanf("%d%d",&out,&in);
totalMuchii+=in;
capacity[src][i]=out;
capacity[n+i][dst]=in;
G[src].push_back(i);
G[i].push_back(src);
G[n+i].push_back(dst);
G[dst].push_back(n+i);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j)
{
capacity[i][n+j]=1;
G[i].push_back(n+j);
G[n+j].push_back(i);
}
}
}
while(1)
{
bfs();
if(viz[dst]==false) break;
for(int next:G[dst])
{
if(viz[next]==false || capacity[next][dst]==flow[next][dst])
continue;
t[dst]=next;
int minFlow=INT_MAX;
for(int nod=dst;nod!=src;nod=t[nod])
minFlow=min(minFlow,capacity[t[nod]][nod]-flow[t[nod]][nod]);
if(minFlow==0)
continue;
for(int nod=dst;nod!=src;nod=t[nod])
{
flow[t[nod]][nod] += minFlow;
flow[nod][t[nod]] -= minFlow;
}
}
}
printf("%d\n",totalMuchii);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j && capacity[i][n + j]==flow[i][n + j])
printf("%d %d\n",i,j);
}
}
return 0;
}