Pagini recente » Cod sursa (job #1539765) | Cod sursa (job #1431452) | Istoria paginii utilizator/m.ana | Cod sursa (job #1153043) | Cod sursa (job #1963515)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct edge
{
int x,y,cap,flow,inv;
};
vector<edge> muc;
vector<int> v[210];
queue<int> q;
int exit[110],enter[110],vaz[210],n,tata[210];
void add_edge(int x,int y,int cap)
{
muc.push_back({x,y,cap,0});
muc.push_back({y,x,0,0});
muc[muc.size()-2].inv=muc.size()-1;
muc[muc.size()-1].inv=muc.size()-2;
v[x].push_back(muc.size()-2);
v[y].push_back(muc.size()-1);
}
int bfs(int S,int D)
{
for(int i=0;i<=2*n+1;i++) vaz[i]=0;
q.push(S);
vaz[S]=1;
while(!q.empty())
{
int nod=q.front();
q.pop();
for(int i=0;i<v[nod].size();i++)
{
int a=v[nod][i];
int vec=muc[a].y;
if(vaz[vec]==0 && muc[a].flow<muc[a].cap)
{
vaz[vec]=1;
tata[vec]=a;
if(vec!=D) q.push(vec);
}
}
}
return vaz[D];
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
int flux=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&exit[i],&enter[i]);
int S=0,D=2*n+1;
for(int i=1;i<=n;i++) add_edge(S,i,exit[i]);
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(i!=j-n) add_edge(i,j,1);
for(int i=n+1;i<=2*n;i++)
add_edge(i,D,enter[i-n]);
while(bfs(S,D))
{
for(int i=0;i<v[D].size();i++)
{
int a=v[D][i];
tata[D]=muc[a].inv;
int s=1e9;
for(int nod=D;nod!=S;nod=muc[tata[nod]].x) s=min(s,muc[tata[nod]].cap-muc[tata[nod]].flow);
for(int nod=D;nod!=S;nod=muc[tata[nod]].x)
{
muc[tata[nod]].flow+=s;
muc[muc[tata[nod]].inv].flow-=s;
}
flux+=s;
}
}
printf("%d\n",flux);
for(int i=0;i<muc.size();i++)
if(muc[i].flow==1 && muc[i].x>=1 && muc[i].x<=n && muc[i].y>=n+1 && muc[i].y<=2*n) printf("%d %d\n",muc[i].x,muc[i].y-n);
return 0;
}