ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1069. Код Прюфера

Have any special test case for this problem??? just WA ,here is my solution
Послано Badd 28 сен 2002 20:59

I know It's a terible code, some idea about using heap
let me know the wrong please.. thank you,

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define maxn 1500
long inp[maxn],top=0,w,c[maxn],p[maxn],htop,outp[maxn];
struct theap { long deg; long i; } h[maxn],temp;
struct tnode { long w; struct tnode* next; };
typedef struct tnode* node;
node head[maxn],last[maxn];
int sort_function( const void *a, const void *b)
{
   if ( (((struct theap*)a)->deg)!=(((struct theap*)b)->deg) )
    return (((struct theap*)a)->deg)-(((struct theap*)b)-
>deg);
   else return (((struct theap*)a)->i)-(((struct theap*)b)->i);
}
int sort_function2( const void *a, const void *b)
{
    return (*(long*)a)-(*(long*)b);
}
long min(long a,long b)
{
    if (a<b) return a; return b;
}
void delheap()
{
    long l;
    h[1]=h[htop];
    h[htop].deg=999999;
    p[h[1].i]=1;
    htop--;
    for (l=1; l*2<=htop; )
    {
        if (min(h[l*2].deg,h[l*2+1].deg)>h
[l].deg) break;
        if (h[l*2].deg<=h[l*2+1].deg)
        {
            temp=h[l];
            h[l]=h[l*2];
            h[l*2]=temp;
            p[h[l].i]=l;
            p[h[l*2].i]=l*2;
            l*=2;
        }else
        {
            temp=h[l];
            h[l]=h[l*2+1];
            h[l*2+1]=temp;
            p[h[l].i]=l;
            p[h[l*2+1].i]=l*2+1;
            l=l*2+1;
        }
    }
    return;
}
void add(long w1,long w2)
{
    node newnode=(node)malloc(sizeof(struct tnode));
    newnode->w=w2; newnode->next=NULL;
    if (head[w1]==NULL) { head[w1]=newnode; last[w1]
=newnode; }
    else
    {
        last[w1]->next=newnode;
        last[w1]=newnode;
    }
    return;
}
int main()
{
    long l,l2,k;
    node nownode;
    FILE* fname=stdin;
    FILE* fout=stdout;
    memset(c,0,sizeof(c));
    for (l=0; l<maxn; l++) h[l].deg=999999;
    while (fscanf(fname,"%ld",&w)!=EOF) { inp[++top]=w; c
[w]++; }
    for (l=1; l<=top+1; l++) { h[l].i=l; h[l].deg=c[l]; head[l]
=NULL; }
    h[0].deg=-1;
    qsort((void *)h, top+1, sizeof(h[0]), sort_function);
    htop=top+1;
    for (l=1; l<=top+1; l++) p[h[l].i]=l;
    for (l=1; l<=top; l++)
    {
        add(inp[l],h[1].i);
        add(h[1].i,inp[l]);
        delheap();
        h[p[inp[l]]].deg--;
        for (l2=p[inp[l]]; l2>1; l2/=2)
        {
            if (h[l2].deg>h
[l2/2].deg) break;
            if (h[l2].deg==h
[l2/2].deg && h[l2/2].i<h[l2].i) break;
            else
            {

    temp=h[l2];
                h[l2]
=h[l2/2];
                h
[l2/2]=temp;
                p[h
[l2].i]=l2;
                p[h
[l2/2].i]=l2/2;
            }
        }
    }
    for (l=1; l<=top+1; l++)
    {
        fprintf(fout,"%ld:",l);
        l2=0;
        for (nownode=head[l]; nownode!
=NULL; nownode=nownode->next)
            outp[++l2]=nownode-
>w;
        outp[0]=-1;
        qsort((void *)outp, l2+1, sizeof(outp[0]),
sort_function2);
        for (k=1; k<=l2; k++) fprintf(fout," %
ld",outp[k]);
        fprintf(fout,"\n");
    }
    return fclose(fname)+fclose(fout);
}