Cod sursa(job #1240965)

Utilizator george_stelianChichirim George george_stelian Data 12 octombrie 2014 13:41:53
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

vector<int> v[210];
queue<int> q;
char vaz[210];
int c[210][210],flow[210][210],tata[210],n,m;

int bfs()
{
    memset(vaz,0,sizeof(vaz));
    q.push(0);
    while(!q.empty())
    {
        int nod=q.front();q.pop();
        for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
            if(!vaz[*it] && c[nod][*it]>flow[nod][*it])
            {
                vaz[*it]=1;
                q.push(*it);
                tata[*it]=nod;
            }
    }
    return vaz[m];
}

int main()
{
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    scanf("%d",&n);
    int sol=0,x,y;
    m=2*n+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        v[0].push_back(i);v[i].push_back(0);
        v[i+n].push_back(m);v[m].push_back(i+n);
        c[0][i]=x;
        c[i+n][m]=y;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
            {
                v[i].push_back(j+n);v[j+n].push_back(i);
                c[i][j+n]=1;
            }
    while(bfs())
    {
        for(vector<int>::iterator it=v[m].begin();it!=v[m].end();it++)
            if(vaz[*it] && c[*it][m]>flow[*it][m])
            {
                tata[m]=*it;
                int s=10000;
                for(int i=m;i;i=tata[i]) s=min(s,c[tata[i]][i]-flow[tata[i]][i]);
                for(int i=m;i;i=tata[i])
                {
                    flow[tata[i]][i]+=s;
                    flow[i][tata[i]]-=s;
                }
                sol+=s;
            }
    }
    printf("%d\n",sol);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j && flow[i][j+n]>0) printf("%d %d\n",i,j);
    return 0;
}