uva125 Numbering Paths

DP, 뻔뻔스럽게 문제보고서 뒤져...
DP가 또 끊겼어요. 문제를 보고 DP라고 생각했어요. 자기가 어떻게 지내야 할지 썼어요. 그리고 고리 문제를 해결할 수 없어요. 마지막에 문제 보고서를 봤어요.
여전히 플로이드를 본떠서 DP를 만들었어요.i에서 j까지 k를 거치면 i에서 j까지의 경로 수는 i에서 k까지의 경로 수에 k에서 j까지의 경로 수를 곱한다
DP가 끝난 후에 모든 점을 스캔한다. 만약에 d[k][k]가 0이 아니라면 k에서 출발하면 k로 돌아갈 수 있다는 뜻이다. (제목은 입력은 자신이 자신의 링에 존재하지 않는다고 했다) 그러면 k점에서 출발하면 최소한의 회로가 존재한다. d[k][k]=-1
그러면 i에서 j까지 만약에 k를 통과하면 무수한 경로가 있다(i에서 k까지, 그리고 회로를 걸어서 k로 돌아가고 다시 k에서 j까지). d[i][j]=-1을
 

#include <cstdio>

#include <cstring>

#define N 35

int n,m;

int d[N][N];



void print_mat(int T)

{

    printf("matrix for city %d
",T);

    for(int i=0; i<=n; i++)

    {

        printf("%d",d[i][0]);

        for(int j=1; j<=n; j++)

            printf(" %d",d[i][j]);

        printf("
");

    }

    return ;

}

void DP()

{

    for(int k=0; k<=n; k++)

        for(int i=0; i<=n; i++)

            for(int j=0; j<=n; j++)

                if(d[i][k] && d[k][j])

                    d[i][j]+=d[i][k]*d[k][j];

    return ;

}

void solve()

{

    for(int k=0; k<=n; k++) if(d[k][k])

    {

        d[k][k]=-1;

        for(int i=0; i<=n; i++)

            for(int j=0; j<=n; j++)

                if(d[i][k] && d[k][j])

                    d[i][j]=-1;

    }

    return ;

}

int main()

{

    int T=0;

    while(scanf("%d",&m)!=EOF)

    {

        memset(d,0,sizeof(d));

        n=-1;

        for(int i=1; i<=m; i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            d[u][v]=1;

            n=u>n?u:n;

            n=v>n?v:n;

        }



        DP();

        solve();

        print_mat(T);

        T++;

    }

    return 0;

}

 
 
증강DP야, 그리고 문제보고서 검색하지 마. 이 문제 조금만 더 참아도 참을 수 있을 것 같아...문제보고서 검색의 죄책감이 너무 아파...