Difference between revisions of "Clasa a XI-a lecția 26"

From Algopedia
Jump to navigationJump to search
(Created page with "==Algoritmul Roy Floyd == [https://infoarena.ro/problema/royfloyd Royfloyd] Se da un graf orientat cu N noduri, memorat prin matricea ponderilor. Sa se determine pentru orice...")
 
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
==Algoritmul Roy Floyd ==
 
==Algoritmul Roy Floyd ==
 
[https://infoarena.ro/problema/royfloyd Royfloyd]
 
[https://infoarena.ro/problema/royfloyd Royfloyd]
Se da un graf orientat cu N noduri, memorat prin matricea ponderilor. Sa se determine pentru orice pereche de noduri x si y lungimea minima a drumului de la nodul x la nodul y si sa se afiseze matricea drumurilor minime. Prin lungimea unui drum intelegem suma costurilor arcelor care-l alcatuiesc.
+
 
 +
Se da un graf orientat cu '''N''' noduri, memorat prin matricea ponderilor. Sa se determine pentru orice pereche de noduri x si y lungimea minima a drumului de la nodul x la nodul y si sa se afiseze matricea drumurilor minime. Prin lungimea unui drum intelegem suma costurilor arcelor care-l alcatuiesc.
  
 
<syntaxhighlight>
 
<syntaxhighlight>
/// doar distanta minima de la un toate nodurile la toate
+
/// doar distanta minima de la toate nodurile la toate
 
/// se afiseaza matricea drumurilor minime rezultate
 
/// se afiseaza matricea drumurilor minime rezultate
 
/// complexitate n^3
 
/// complexitate n^3
Line 24: Line 25:
 
void roy_floyd(){
 
void roy_floyd(){
 
   int i, j, k;
 
   int i, j, k;
   for (k = 1; k <= n; k++)
+
   for ( k = 1; k <= n; k++ )
     for (i = 1; i <= n; i++)
+
     for ( i = 1; i <= n; i++ )
       for (j = 1; j <= n; j++)
+
       for ( j = 1; j <= n; j++ )
         if (a[i][k] && a[k][j] && (a[i][j] > a[i][k] + a[k][j] || !a[i][j]) && i != j)
+
         if ( i != j && a[i][k] && a[k][j] && ( a[i][j] > a[i][k] + a[k][j] || !a[i][j] ) )
 
           a[i][j] = a[i][k] + a[k][j];
 
           a[i][j] = a[i][k] + a[k][j];
 
}
 
}
Line 33: Line 34:
 
void afis(){
 
void afis(){
 
   int i, j;
 
   int i, j;
   for (i = 1; i <= n; i++) {
+
   for ( i = 1; i <= n; i++ ) {
     for (j = 1; j <= n; j++) printf("%d ",a[i][j]);
+
     for ( j = 1; j <= n; j++ )  
     printf("\n");
+
      printf( "%d ",a[i][j] );
 +
     printf( "\n" );
 
   }
 
   }
 
}
 
}
Line 49: Line 51:
  
 
[https://infoarena.ro/problema/r Roy Floyd]
 
[https://infoarena.ro/problema/r Roy Floyd]
Aceeasi problema. Vom afisa suplimentar, pe langa matricea cu drumurile minime de la oricare doua nori si o a doua matrice ce va retine cate strazi maxim pargurg pe drumurile minime.
+
Aceeasi problema. Vom afisa suplimentar, pe langa matricea cu drumurile minime de la oricare doua noduri si o a doua matrice ce va retine cate strazi maxim pargurg pe drumurile minime.
 
<syntaxhighlight>
 
<syntaxhighlight>
 
#include <bits/stdc++.h>
 
#include <bits/stdc++.h>
Line 62: Line 64:
 
   
 
   
 
void citire() {
 
void citire() {
     f >> n;
+
  f >> n;
 +
  for( int i = 1; i <= n; i++ )
 +
     for( int j = 1; j <= n; j++ ) {
 +
      f >> a[i][j];
 +
      if( i != j )
 +
        b[i][j] = 1;
 +
    }
 +
}
 
   
 
   
 +
void roy() {
 +
  for(int k=1; k<=n; k++)
 
     for(int i=1; i<=n; i++)
 
     for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) {
+
      for(int j=1; j<=n; j++)
            f >> a[i][j];
+
        if((a[i][j] > a[i][k] + a[k][j]) or (a[i][j] == a[i][k] + a[k][j] and b[i][j] < b[i][k] + b[k][j])) {
+
          b[i][j] = b[i][k] + b[k][j];
            if(i != j) b[i][j] = 1;
+
          a[i][j] = a[i][k] + a[k][j];
 
         }
 
         }
}
 
 
void roy() {
 
    for(int k=1; k<=n; k++)
 
        for(int i=1; i<=n; i++)
 
            for(int j=1; j<=n; j++)
 
                if((a[i][j] > a[i][k] + a[k][j]) or (a[i][j] == a[i][k] + a[k][j] and b[i][j] < b[i][k] + b[k][j])) {
 
                    b[i][j] = b[i][k] + b[k][j];
 
                    a[i][j] = a[i][k] + a[k][j];
 
                }
 
 
}
 
}
 
   
 
   
 
void afisare() {
 
void afisare() {
    for(int i=1; i<=n; i++) {
+
  for( int i = 1; i <= n; i++ ) {
        for(int j=1; j<=n; j++)
+
    for(int j = 1; j <= n; j++ )
            g << a[i][j] << " ";
+
      g << a[i][j] << " ";
        g << "\n";
+
      g << "\n";
    }
+
  }
+
  for( int i = 1; i <= n; i++ ) {
    for(int i=1; i<=n; i++) {
+
    for( int j = 1; j <= n; j++ )
        for(int j=1; j<=n; j++)
+
      g << b[i][j] << " ";
            g << b[i][j] << " ";
+
      g << "\n";
            g << "\n";
 
 
     }
 
     }
 
}
 
}
 
   
 
   
 
int main() {
 
int main() {
    citire();
+
  citire();
    roy();
+
  roy();
    afisare();
+
  afisare();
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 
= Tema =  
 
= Tema =  
 
Pbinfo
 
Pbinfo

Latest revision as of 10:53, 23 March 2020

Algoritmul Roy Floyd

Royfloyd

Se da un graf orientat cu N noduri, memorat prin matricea ponderilor. Sa se determine pentru orice pereche de noduri x si y lungimea minima a drumului de la nodul x la nodul y si sa se afiseze matricea drumurilor minime. Prin lungimea unui drum intelegem suma costurilor arcelor care-l alcatuiesc.

/// doar distanta minima de la toate nodurile la toate
/// se afiseaza matricea drumurilor minime rezultate
/// complexitate n^3
#include <stdio.h>

int n, a[105][105];

void citire(){
  freopen("royfloyd.in","r",stdin);
  freopen("royfloyd.out","w",stdout);

  int i, j;
  scanf( "%d", &n);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      scanf("%d",&a[i][j]);
}

void roy_floyd(){
  int i, j, k;
  for ( k = 1; k <= n; k++ )
    for ( i = 1; i <= n; i++ )
      for ( j = 1; j <= n; j++ )
        if ( i != j && a[i][k] && a[k][j] && ( a[i][j] > a[i][k] + a[k][j] || !a[i][j] ) )
          a[i][j] = a[i][k] + a[k][j];
}

void afis(){
  int i, j;
  for ( i = 1; i <= n; i++ ) {
    for ( j = 1; j <= n; j++ ) 
      printf( "%d ",a[i][j] );
    printf( "\n" );
  }
}
int main(){
  citire();
  roy_floyd();
  afis();
  return 0;
}


Roy Floyd Aceeasi problema. Vom afisa suplimentar, pe langa matricea cu drumurile minime de la oricare doua noduri si o a doua matrice ce va retine cate strazi maxim pargurg pe drumurile minime.

#include <bits/stdc++.h>
using namespace std;
 
ifstream f("rf.in");
ofstream g("rf.out");
 
const int N = 1001;
int a[N][N], b[N][N];
int n;
 
void citire() {
  f >> n;
  for( int i = 1; i <= n; i++ )
    for( int j = 1; j <= n; j++ ) {
      f >> a[i][j]; 
      if( i != j ) 
        b[i][j] = 1;
    }
}
 
void roy() {
  for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
        if((a[i][j] > a[i][k] + a[k][j]) or (a[i][j] == a[i][k] + a[k][j] and b[i][j] < b[i][k] + b[k][j])) {
          b[i][j] = b[i][k] + b[k][j];
          a[i][j] = a[i][k] + a[k][j];
        }
}
 
void afisare() {
  for( int i = 1; i <= n; i++ ) {
    for(int j = 1; j <= n; j++ )
      g << a[i][j] << " ";
      g << "\n";
  }
  for( int i = 1; i <= n; i++ ) {
    for( int j = 1; j <= n; j++ )
       g << b[i][j] << " ";
       g << "\n";
    }
}
 
int main() {
  citire();
  roy();
  afisare();
}

Tema

Pbinfo

Infoarena