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

Обсуждение задачи 1099. Work Scheduling

who can give me some wa data??although I know my solution is wa.
Послано ben3ben 17 апр 2012 15:06
#include <cstdio>
#include <string.h>

using namespace std;

struct dat_edge
{
    int last,aim;
}edge[500000];
int temp[300],len_edge,pl[300],next[300],n,m;

void edge_insert(int x,int y)
{
    len_edge++;
    edge[len_edge].aim=y;
    edge[len_edge].last=pl[x];
    pl[x]=len_edge;
}

bool dfs(int root,int ps)
{
    if (temp[root]==ps) return false;
    if (ps==-1) return true;
    temp[root]=ps;
    int p=pl[root];
    bool t;
    while (p!=-1)
    {
        int tmp=edge[p].aim;
        if (temp[tmp]==ps) { p=edge[p].last;continue; }
        if (next[tmp]==-1) t=dfs(tmp,-1); else t=dfs(next[tmp],ps);
        if (t)
        {
            next[root]=edge[p].aim;
            next[edge[p].aim]=root;
            return true;
        }
        p=edge[p].last;
    }
    return false;
}

int main()
{
    //freopen("1099.in","r",stdin);
    //freopen("1099.out","w",stdout);
    int i,j,k,ans,coun,x,y;
    bool ok;
    scanf("%d",&n);
    len_edge=-1;
    for (i = 0;i<=n;i++) pl[i]=-1;
    while (scanf("%d%d",&x,&y)!=EOF)
    {
        edge_insert(x,y);
        edge_insert(y,x);
    }
    coun=0;
    for (i = 0;i<=n;i++) next[i]=-1;
    memset(temp,0,sizeof(temp));
    ans=0;
    for (i = 1;i<=n;i++)
    {
        ok=false;
        if (next[i]==-1) ok=dfs(i,++coun);
        if (ok) ans++;
    }
    printf("%d\n",ans*2);
    for (i = 1;i<=n;i++)
    if (next[i]>i)
    {
        printf("%d %d\n",i,next[i]);
    }
}
Re: who can give me some wa data??although I know my solution is wa.
Послано ben3ben 17 апр 2012 17:00
15
1 7
10 9
7 1
5 2
1 6
13 8
13 15
2 3
3 6
10 14
5 5
11 15
1 3
13 5
15 3
13 2

ans:12