Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 1 KB
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;
}
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)