Informatika gyűjtemény

Egy szinttel feljebb folyam.cpp

2004050607080910

<<  25. óra  >>

<<  Feladatok  >>

NézetNyomtat

folyam.cpp (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 1 KB
/*
    Informatika: algoritmus szakkör
    24. óra
    1. feladat: Folyam algoritmus
    Uray M. János, 2009. március 17.
*/
#include <stdio.h>
#include <matrix.h>
#define MaxNum 1000
#define MaxCap 20

cMatrix Graph;
int Source, Dest, Num;

int Read (char *);
int Write (char *);
int FindOpt (void);
int FindRoute (int, int *);

int main (int AN, char * Args []) {
    if (AN < 3)
        return 1;
    if (!Read(Args[1]))
        return 1;
    if (!Write(Args[2]))
        return 1;
    return 0;
}

int Read (char * FN) {
    FILE * F = fopen(FN, "rt");
    int E, U, V, C;
    
    if (F == NULL)
        return 0;
    fscanf(F, "%d", &Num);
    Graph.Set(Num, Num);
    Graph.Empty();
    fscanf(F, "%d %d", &Source, &Dest);
    Source--;
    Dest--;
    fscanf(F, "%d", &E);
    for (int I = 0; I < E; I++) {
        fscanf(F, "%d %d %d", &U, &V, &C);
        Graph.SetItem(U - 1, V - 1, C);
    }
    fclose(F);
    return 1;
}

int Write (char * FN) {
    FILE * F = fopen(FN, "wt");
    
    if (F == NULL)
        return 0;
    fprintf(F, "%d", FindOpt());
    fclose(F);
    return 1;
}

// Optimum keresése
int FindOpt (void) {
    // Útvonal elemei, aktuális indexe
    int R[MaxNum], Opt = 0, Min, I;
    
    while (1) {
        // Útvonal keresése a maradékgráfban (ha nincs, akkor megtaláltuk az optimumot)
        for (I = 0; I < Num; I++)
            R[I] = -1;
        if (!FindRoute(Source, R))
            break;
        // A legkisebb útkeresztmetszet megkeresése
        Min = MaxCap;
        for (I = Source; I != Dest; I = R[I])
            if (Graph.GetItem(I, R[I]) < Min)
                Min = Graph.GetItem(I, R[I]);
        // A gráf csökkentése az aktuális úttal
        for (I = 0; I < Num; I++)
            if (R[I] != -1) {
                Graph.GetItem(I, R[I]) -= Min;
                Graph.GetItem(R[I], I) += Min;
            }
        // Az optimum változtatása az újonnan bevezetett út keresztmetszetével
        Opt += Min;
    }
    return Opt;
}
int FindRoute (int A, int * R) {
    for (int I = 0; I < Num; I++)
        if (R[I] == -1 && Graph.GetItem(A, I)) {
            R[A] = I;
            if (I == Dest || FindRoute(I, R))
                return 1;
        }
    R[A] = -1;
    return 0;
}
(Vissza)