Cod sursa(job #1027581)

Utilizator dariusdariusMarian Darius dariusdarius Data 12 noiembrie 2013 21:13:12
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> G[205];
int C[205][205];
int F[205][205];
int N,P[205];
queue<int> Q;
bool bfs()
{
    for(int i=1;i<=2*N+1;i++)
        P[i]=-1;
    Q.push(0);P[0]=0;
    while(!Q.empty())
    {
        for(vector<int>::iterator it=G[Q.front()].begin();it!=G[Q.front()].end();it++)
            if(P[*it]==-1 && F[Q.front()][*it]<C[Q.front()][*it])
            {
                P[*it]=Q.front();
                Q.push(*it);
            }
        Q.pop();
    }
    if(P[2*N+1]!=-1)
        return true;
    return false;
}
int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&N);
    for(int a,b,i=1;i<=N;i++)
    {
        scanf("%d%d",&a,&b);
        G[0].push_back(i);
        G[i].push_back(0);
        G[N+i].push_back(2*N+1);
        G[2*N+1].push_back(N+i);
        C[0][i]=a;C[N+i][2*N+1]=b;
        for(int j=1;j<=N;j++)
            if(i!=j)
            {
                C[i][N+j]=1;
                G[i].push_back(N+j);
                G[N+j].push_back(i);
            }
    }
    int total=0;
    while(bfs())
    {
        int u=2*N+1,flux=1000000000;
        while(u!=0)
        {
            flux=min(flux,C[P[u]][u]-F[P[u]][u]);
            u=P[u];
        }
        u=2*N+1;
        while(u!=0)
        {
            F[P[u]][u]+=flux;
            F[u][P[u]]-=flux;
            u=P[u];
        }
        total+=flux;
    }
    printf("%d\n",total);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            if(F[i][N+j])
                printf("%d %d\n",i,j);
    return 0;
}