Cod sursa(job #1963548)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 12 aprilie 2017 16:55:14
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct edge
{
    int x,y,cap,flow,inv;
};

vector<edge> muc;
vector<int> v[210];
queue<int> q;
int out[110],in[110],vaz[210],n,tata[210];

void add_edge(int x,int y,int cap)
{
    int a=muc.size();
    muc.push_back({x,y,cap,0,a+1});
    muc.push_back({y,x,0,0,a});
    v[x].push_back(a);
    v[y].push_back(a+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;
                if(vec!=D) q.push(vec);
                tata[vec]=a;
            }
        }
    }
    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",&out[i],&in[i]);
    int S=0,D=2*n+1;
    for(int i=1;i<=n;i++) add_edge(S,i,out[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,in[i-n]);
    while(bfs(S,D))
    {
        for(int i=0;i<v[D].size();i++)
        {
            int a=muc[v[D][i]].inv;
            if(vaz[muc[a].x]==0 or muc[a].flow==muc[a].cap) continue;
            tata[D]=a;
            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;
}