Cod sursa(job #1144234)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 16 martie 2014 19:47:02
Problema Taramul Nicaieri Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <bitset>
#include <queue>

#define super_start 0
#define super_sink 2*N+1
#define Nmax 205
#define INF 0x3f3f3f3f

using namespace std;

int N,maxFLOW;
int flow[Nmax][Nmax],capacity[Nmax][Nmax],daddy[Nmax];
vector<int> G[Nmax];
bitset<Nmax> used;
queue<int>Q;
int A[Nmax],B[Nmax];

inline void pre_compute()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i)
        scanf("%d%d",&A[i],&B[i]);

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(i != j && A[i] && B[j])
            {
                G[i].push_back(j+N);
                G[j+N].push_back(i);
                capacity[i][j+N] = 1;
                capacity[j+N][i] = 1;
            }
    int a,b;
    for(int i = 1; i <= N; ++i)
    {
        if(A[i])
        {
            G[super_start].push_back(i);
            G[i].push_back(super_start);
             capacity[super_start][i] = A[i];
        }
        if(B[i])
        {
            G[super_sink].push_back(i+N);
            G[i+N].push_back(super_sink);
            capacity[i+N][super_sink] = B[i];
        }
    }
}

inline bool BFS(int k)
{
    used = 0;
    used[k] = 1;
    Q.push(k);
    while(!Q.empty())
    {
        k = Q.front();Q.pop();
        if(k == super_sink) continue;
        for(vector<int>::iterator it = G[k].begin(); it != G[k].end(); ++it)
            if(!used[*it] && capacity[k][*it] - flow[k][*it] != 0)
            {
                used[*it] = 1;
                daddy[*it] = k;
                Q.push(*it);
            }
    }
    return used[super_sink] != 0;
}

inline void FLOW()
{
    int minFLOW;
    while(BFS(super_start))
    for(vector<int>::iterator it = G[super_sink].begin(); it != G[super_sink].end(); ++it)
    {
        if(!used[super_sink] || capacity[*it][super_sink] == flow[*it][super_sink]) continue;
        daddy[super_sink] = *it;
        minFLOW = INF;
        for(int nodc = super_sink;nodc; nodc = daddy[nodc])
            minFLOW = min (minFLOW,capacity[daddy[nodc]][nodc] - flow[daddy[nodc]][nodc]);
        for(int nodc = super_sink;nodc; nodc = daddy[nodc])
        {
            flow[daddy[nodc]][nodc] += minFLOW;
            flow[nodc][daddy[nodc]] -= minFLOW;
        }
        maxFLOW += minFLOW;
    }
}

void print()
{
    printf("%d\n",maxFLOW);
    for(int i = 1; i <= N; ++i)
        for(int j = 1+N; j <= 2*N; ++j)
            if(flow[i][j] > 0)
                printf("%d %d\n",i,j-N);
}

int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);

    pre_compute();
    FLOW();
    print();

    return 0;
}