Отримання знань

дистанційна підтримка освіти школярів


Сортировка всего этого
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#include< stdio.h >
#include< string.h >
int n,m;
int g[30][30];
int use[30];
int num;
void floyd()
{
    for(int k=0; k < n; k++)   
        for(int j=0; j < n; j++)
            for(int i=0; i < n; i++)
                if(g[j][k] && g[k][i])
                    g[j][i]=1;
}
int con()
{
    for(int i=0; i < n; i++)
        for(int j=0; j < n; j++)
            if(g[i][j] && g[j][i])
                {
                    printf("Inconsistency found after %d relations.\n",num);
                    return 1;
                }
        return 0;
}
int isok()
{
    int flag[30][30];
    int t=0,i,j;
    memcpy(flag,g,sizeof(g));
    memset(use,0,sizeof(use));
    while(++t <= n)
    {
        int count=0;
        int temp;
        for(i=0; i < n; i++)
        if(use[i]==0)
        {
            int flag1=1;
            for(j=0; j < n; j++)
                flag1*=!flag[j][i];
            if(flag1)
            {
                count++;
                temp=i;
            }
        }
        if(count > 1)
        return 0;
        for(int i=0; i < n; i++)
            flag[temp][i]=0;
        use[temp]=t;
    }
    printf("Sorted sequence determined after %d relations: ",num);
    for(int i=1; i <= n; i++)
        for(int j=0; j < n; j++)
            if(use[j]==i)
                printf("%c",j+'A');
    printf(".\n");
    return 1;
}
void init()
{
    int d=0;
    char a,b,c;
    memset(g,0,sizeof(g));
    for(int i=1; i <= m; i++)
        {
            num=i;
            scanf("%c%c%c",&a,&b,&c);
            getchar();
            g[a-'A'][c-'A']=1;
            if(d)
            continue;
            floyd();
            if(con())
            d=1;
            if(d==0)
            if(isok())
            d=1;
        }
    if(d==0)
    printf("Sorted sequence cannot be determined.\n");
}
int main()
{
    while(scanf("%d%d",&n,&m)&&n)
    {
        getchar();
        init();
    }
    return 0;
}
 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)