Cod sursa(job #1963515)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 12 aprilie 2017 16:26:30
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#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;
}