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

Обсуждение задачи 1182. Team Them Up!

And in this one, what's wrong???
Послано ijk 23 мар 2002 05:44
#include<iostream.h>
#include<stdlib.h>

#define NONE -1
#define ONE 0
#define TWO 1

class Queue
{
 private:
    short last,first;
    short q[100];
 public:
    Queue(){first=last=-1;}
    void push(short a) { last=(last+1)%100; q[last]=a; }
    short pop() { first=(first+1)%100; return q[first]; }
    char empty(){return (first==last);}
};

short N;
char  notknow[100][100];
short team[100];
short reach[100];
short in1, in2;
short one[100];

void color(short i, short COL)
{
short j, k;
Queue queue;
    reach[i]++;
    team[i]=COL;
    if (team[i]==ONE) one[i]++;
    queue.push(i);
        while (!queue.empty())
        {
            j = queue.pop();
            for (k=0; k<N; k++)
                if (notknow[j][k]==1)
                {
                    if (team[k]==NONE)
                    {
                        reach[i]++;
                        team[k]=(team[j]+1)%2;
                        if (team[k]==ONE)
one[i]++;
                        queue.push(k);
                        continue;
                    }
                    if (team[k]==team[j])
                    {
                        cout<<"No solution";
                        exit(0);
                    }
                }
        }
}

void main()
{
short i, j, pos;
    cin>>N;
    for (i=0; i<N; i++)
        for (j=0; j<N; j++) notknow[i][j]=1;
    for (i=0; i<N; i++) notknow[i][i]=0;
    for (i=0; i<N; i++)
    {
        cin>>j;
        while (j>0)
        {
            notknow[i][j-1]=0;
            cin>>j;
        }
    }
    for (i=0; i<N; i++)
        for (j=0; j<N; j++)
            if (notknow[i][j]==1)
                 notknow[j][i]= 1;
    for (i=0; i<N; i++)
    {
        reach[i]=0;
        one[i]=0;
        team[i]=NONE;
    }
    for (i=0; i<N; i++)
        if (team[i]==NONE) color(i,ONE);
int name[100], h;
    for (i=0; i<N; i++)
        name[i]=i;
    for (i=0; i<N-1; i++)
    {
        pos=i;
        for (j=i+1; j<N; j++)
            if (one[j]>one[pos])pos=j;
        if (pos!=i)
        {
            h=name[i], name[i]=name[pos], name[pos]=h;
            h=reach[i],reach[i]=reach[pos],reach[pos]=h;
            h=one[i], one[i]=one[pos], one[pos]=h;
        }
    }
    in1 = 0;
    in2 = 0;
    for (i=0; i<N; i++) team[i]=NONE;
 for (i=0; i<N; i++)
    if (team[name[i]]==NONE)
    {
        if (in1>in2)
        {
            if (one[i]>=reach[i]-one[i])
            {
                in2+=one[i];
                in1+=(reach[i]-one[i]);
                color(name[i],TWO);
            }
        else
            {
                in2+=(reach[i]-one[i]);
                in1+=one[i];
                color(name[i],ONE);
            }
        }
        else
        {
            if (one[i]>=reach[i]-one[i])
            {
                in1+=one[i];
                in2+=(reach[i]-one[i]);
                color(name[i],ONE);
            }
        else
            {
                in1+=(reach[i]-one[i]);
                in2+=one[i];
                color(name[i],TWO);
            }
        }
    }
    cout<<in1<<" ";
    for (i=0; i<N; i++)
        if (team[i]==ONE)
            cout<<(i+1)<<" ";
    cout<<endl;
    cout<<in2<<" ";
    for (i=0; i<N; i++)
        if (team[i]==TWO)
            cout<<(i+1)<<" ";
}