Cod sursa(job #164209)

Utilizator FlorinC1996Florin C FlorinC1996 Data 23 martie 2008 17:49:56
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
 #include <stdio.h>   
#include <limits.h>   
#include <vector>   
#include <queue>   
  
using namespace std;   
  
#define MN (209)   
#define pb push_back   
  
int c[MN][MN], f[MN][MN], p[MN], m[MN];   
vector<int> g[MN];   
int N, F, S = 0, D;   
queue<int> q;   
  
int bfs(int s, int t)   
{   
    int n1, n2, i;   
  
    memset(p, -1, sizeof(p));   
    memset(m, 0, sizeof(m));   
    m[s] = LONG_MAX;   
    for(; !q.empty(); q.pop());   
    for(q.push(s); !q.empty(); q.pop()) {   
        n1 = q.front();   
        for(i = 0; i < g[n1].size(); ++ i) {   
            n2 = g[n1][i];   
            if(c[n1][n2]-f[n1][n2] > 0 && p[n2] == -1) {   
                m[n2] = min(m[n1], c[n1][n2]-f[n1][n2]);   
                p[n2] = n1;   
                if(n2 != t)   
                    q.push(n2);   
                else return m[t];   
            }   
        }   
    }   
    return m[t];   
}   
  
void ek()   
{   
    int n1, n2;   
    for(; bfs(S, D); F += m[D]) {   
        for(n1 = D; n1 != S; n1 = n2) {   
            n2 = p[n1];   
            f[n2][n1] += m[D];   
            f[n1][n2] -= m[D];   
        }   
    }   
}   
  
int main()   
{   
    int i, j;   
  
    freopen("harta.in", "r", stdin);   
    freopen("harta.out", "w", stdout);   
  
    scanf("%d", &N);   
    for(D = 2*N+1, i = 1; i <= N; ++ i) {   
        g[0].pb(i); g[i].pb(0); scanf("%d", &c[0][i]);   
        g[N+i].pb(D); g[D].pb(N+i); scanf("%d", &c[N+i][D]);   
    }   
  
    for(i = 1; i <= N; ++ i) for(j = 1; j <= N; ++ j) if(i != j) {   
        g[i].pb(N+j); c[i][N+j] = 1;   
        g[N+j].pb(i);   
    }   
  
    /*  
    for(i = 0; i <= D; ++ i, printf("\n")) for(printf("%d:", i), j = 0; j < g[i].size(); ++ j)  
        printf(" %d", g[i][j]);  
    for(i = 0; i <= D; ++ i, printf("\n")) for(j = 0; j <= D; ++ j)  
        printf("%d ", c[i][j]);  
    for(i = 0; i <= D; ++ i, printf("\n")) for(j = 0; j <= D; ++ j)  
        printf("%d ", f[i][j]);  
        */  
  
    ek();   
  
    /*  
    for(printf("%d\n", F), i = 0; i <= D; ++ i, printf("\n")) for(printf("%d:", i), j = 0; j <= D; ++ j)  
        printf(" %d", f[i][j]);  
        */  
  
    printf("%d\n", F);   
    for(i = 1; i <= N; ++ i) for(j = 1; j <= N; ++ j) if(f[i][N+j] > 0)   
        printf("%d %d\n", i, j);   
  
    return 0;   
}