564 Rfinv

[•PlayLikeNeverB4]

Cod:

if(a[i][j]!=0 || a[i][j]!=inf)

Vezi conditia asta.

[•MIrcea_Gheoace]

Nu știu care este problem la rezolvarea mea: Am încercat cu ideea lui Filip

Eu am facut un pic altfel ( de fapt e acelasi lucru cu solutia oficiala dar e formulat altfel ):

* pentru fiecare pereche (i j) trebuie sa am A[ i ][ j ] <= A[ i ][ k ] + A[ k ][ j ] pentru orice k. Daca exista un k pt. care A[ i ][ k ] + A[ k ][ j ] < A[ i ][ j ] => nu am solutie
* daca exista o pereche (i j) pt. care nu exista nici un k a. i. A[ i ][ j ] = A[ i ][ k ] + A[ k ][ j ] si nu am muchie de la i la j in graf => nu am solutie

Eu am facut asa si am obtinut 100 .

Și am mi-a rezultat asa:
# include <cstdio>
# include <cstring>
using namespace std;
FILE *f=fopen("rfinv.in","r"),*g=fopen("rfinv.out","w");
short n,m,t,i,j;
bool A[51][51],C[51][51];int B[51][51];
/*
A matrice de adiacenta in care A[j]=1 daca exista legatura intre i si j si 0 altfel
C matrice in care salvez 1 daca exista drum intre i si j sau costul dintre i si j poate fi descompus pe drumul i->k k->j
B matricea unde se afla rezultatul royfloyd din fisier
*/
bool royfloyd()
{
    short i,j,k;
    for(k=1;k<=n;++k)
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
            if(i!=j)
         {
                if(B[j] > B[k]+B[k][j])
                    return 0;
            if(A[j] || B[j]==B[k]+B[k][j])
               C[j]=1;
         }
   for(i=1;i<=n;++i)
      for(j=1;j<=n;++j)
         if(i!=j)
            if(!C[j])//daca exista drum si nu nu este pe diag princ
               return 0;
   return 1;
}
template<class T>
void initMatrice(T A[][51])
{
    for(i=0;i<n;++i)
        memset(A,0,(n+1)*sizeof(T));
}
int main()
{
    fscanf(f,"%hd",&t);
    while(t--)
    {
        fscanf(f,"%hd %hd\n",&n,&m);
        initMatrice(A);
      initMatrice(B);
      initMatrice(C);
        short x,y;
        for(i=0;i<m;++i)
        {
            fscanf(f,"%hd %hd\n",&x,&y);
            A

• [y]=A[y]
• =1;

        }
        for(i=1;i<=n;++i)
         for(j=1;j<=n;++j)
            fscanf(f,"%d",B+j);
        if(royfloyd())
            fprintf(g,"DA\n");
        else
            fprintf(g,"NU\n");
    }
}
Primesc mesajul Incorect

[•jason2013]

Imi poate spune cineva unde gresesc de imi da testul " incorect " ? >.>
PS: Am luat multe teste cu solutia asta, daca aveti cazuri exceptate dati-mi-le.. Multumesc !

#include <bits/stdc++.h>
#define inf 1000001
using namespace std;

ifstream f("rfinv.in");
ofstream g("rfinv.out");

const int NMAX = 51;
int t, n, m, counter;
int a[NMAX][NMAX], c[NMAX][NMAX];

void citire()
{
    f>>n>>m;

    for(int i = 1; i<= n; i++)
        for(int j =1; j <= n; j++)
        {
            if(i != j) a[j] = inf;
        }

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        f>>x>>y;
        a

• [y] = 1;

        a[y]

• = 1;

    }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <=n; j++)
        {
            f>>c[j];
            if(a[j] || a[j] == inf)
                a[j] = c[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 && i != k && j != k && a[j] > a[k] + a[k][j] && a[j] )
                {
                    a[j] = a[k] + a[k][j];
                    counter++;
                }
}

void afisare()
{
    for(int i = 1; i <= n; i++)
    {

        for(int j = 1; j <= n; j++)
            g<<a[j]<<" ";
        g<<"\n";
    }

}

int main()
{
    f>>t;
    for(int i = 1; i <= t; i++)
    {
        int greseli = 0;
        counter = 0;
        citire();
        afisare();
        g<<"\n";
        roy_floyd();

        if(counter != 0)
            g<<"NU" <<"\n";
        else
        {
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    if(a[j] != c[j])
                        greseli++;
            if(greseli != 0)
                g<<"NU"<<"\n";
            else g<<"DA"<<"\n";
        }

    }
    return 0;
}