Cod sursa(job #251826)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 3 februarie 2009 14:03:43
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
# include <cstdio>
# include <algorithm>

using namespace std;

# define FIN "harta.in"
# define FOUT "harta.out"
# define MAXN 105

int N, source, sink;
int T[MAXN];
int Stack[MAXN];
int C[MAXN][MAXN];

    int BFS()
    {
        int i, j, vf;
        
        Stack[vf = 1] = source;
        memset(T, 0, sizeof(T));
        
        for (i = 1; i <= vf; ++i)
          for (j = 1; j <= sink; ++j)
            if (!T[j] && C[Stack[i]][j])
            {
               T[j] = Stack[i];
               Stack[++vf] = j;
               if (j == sink) return 1;
            }
        
        return 0;
    }

    void flow()
    {
        int tflx = 0, i, j;
        
        for (; BFS();)
        {
            for (int i = sink; i != source; i = T[i])
            {
                C[T[i]][i] --;
                C[i][T[i]] ++;
            }
            
            tflx ++;
        }
        
        printf("%d\n",tflx);
        
        for (i = 1; i <= N; ++i)
          for (j = 1; j <= N; ++j)
            if (C[j + N][i]) printf("%d %d\n",i, j);    
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d",&N);
        
        source = 0; sink = 2 * N + 1;        
        for (int i = 1; i <= N; ++i)
        {
            int x, y;
            scanf("%d%d",&x, &y);
            
            C[source][i] = x;
            C[i + N][sink] = y;
        }
        
        for (int i = 1; i <= N; ++i)
          for (int j = 1; j <= N; ++j)
            if (i != j) C[i][j + N] = 1;
            
        flow();
        
        return 0;
    }