Informatika gyűjtemény

Egy szinttel feljebb uj_h1n1.cpp

2004050607080910

<<  11. óra  >>

<<  Járvány  >>

NézetNyomtat

uj_h1n1.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: us-ascii
Méret: 2 KB
/*
    Informatika: algoritmus szakkor
    Feladat: H1N1 Jarvany
    Forras: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/11ora/jarvany
    Uray M. Janos, 2009. december 1.
*/
#include <stdio.h>
#include <time.h>

#define MaxN 30
#define MaxM 435

typedef unsigned char byte;
typedef unsigned short int word;
typedef unsigned long int dword;

int N, M;
// A beolvasott utak a varosok kozott
byte Route[MaxM][2];
// Az egyes varosok lefedese (szomszedok es onmaga) bitmaszkban
dword Bitmask[MaxN];
// Valtozo, mely a teljes lefedest tarolja
dword Full;

bool Read (const char *);
void MakeBitmasks (void);
void Backtrack (dword, int, int, int &);
void Print (void);

int main (int AN, char * Args []) {
    int Min;
    clock_t T;
    
    // Parameterek ellenorzese, beolvasas
    if (AN < 2)
        return 1;
    if (!Read(Args[1]))
        return 1;
    
    // Bitmaszkok elkeszitese
    MakeBitmasks();
    
    // Backtrack inditasa, idomeres
    T = clock();
    Min = N;
    Backtrack(0, 0, 0, Min);
    T = clock() - T;
    
    // Eredmeny es ido kiirasa
    printf("%d\n", Min);
    printf("Time: %.2f s\n", (1.0 * T) / CLOCKS_PER_SEC);
    
    return 0;
}

// Fajlbol olvasas
bool Read (const char * FN) {
    FILE * F = fopen(FN, "r");
    if (F == NULL)
        return false;
    fscanf(F, "%d %d\n", &N, &M);
    for (int I = 0; I < M; I++) {
        fscanf(F, "%d %d\n", &Route[I][0], &Route[I][1]);
        // A C++ 0-tol indexel, a bemenet pedig 1-tol
        Route[I][0]--;
        Route[I][1]--;
    }
    fclose(F);
    return true;
}

// A beolvasott adatok alapjan elkesziti a bitmaszkokat
void MakeBitmasks (void) {
    int I, J;
    // Minden egyes varosra megkeresi az osszes utat, amelynek vegpontja az a varos,
    // es azt hozzaadja a bitmaszkhoz.
    // A bitmaszkot az onmaganak megfelelo helyiertekkel inicializaljuk.
    for (I = 0; I < N; I++) {
        Bitmask[I] = 1 << I;
        for (J = 0; J < M; J++) {
            if (Route[J][0] == I)
                Bitmask[I] |= 1 << Route[J][1];
            else if (Route[J][1] == I)
                Bitmask[I] |= 1 << Route[J][0];
        }
    }
    // A teljes lefedes
    Full = (1 << N) - 1;
}

// A backtrack fuggveny
// Covered: az eddig lefedett varosok bitmaszkban
// Depth: a keresesi melyseg (azaz a oltoallomasokkal felszerelt varosok szama)
// X: azon varos sorszama, amelytol a kereses indulhat
// Min: az eddigi minimalis varosszam (cim szerinti parameteratadassal)
void Backtrack (dword Covered, int Depth, int X, int & Min) {
    // Ha mar lefedett mindent, akkor befejezte a keresest
    if (Covered == Full) {
        if (Depth < Min)
            Min = Depth;
        return;
    }
    // Tovabbi varosok keresese, amelyek lefednek valami ujat is
    for (int I = X; I < N; I++)
        if ((Covered & Bitmask[I]) != Bitmask[I])
            Backtrack(Covered | Bitmask[I], Depth + 1, I + 1, Min);
}

// Bitmaszkok kiirasa
void Print (void) {
    int I, J;
    for (I = 0; I < N; I++) {
        for (J = 0; J < N; J++)
            printf("%d", Bitmask[I] & (1 << J) ? 1 : 0);
        printf("\n");
    }
}
(Vissza)