poj1033

模拟题，注意不需要移动的情况要特殊输出

#include <cstdio>

#include <cstring>

#include <cstdlib>

using namespace std;

#define MAX_CLUSTER_NUM 10005

int cluster_num, file_num;

int link[MAX_CLUSTER_NUM];

bool is_free[MAX_CLUSTER_NUM];

int total_length;

bool optimized;

void input()

{

    memset(link, -, sizeof(link));

    scanf("%d%d", &cluster_num, &file_num);

    for (int i = ; i < cluster_num; i++)

        is_free[i] = true;

    int target_pos = ;

    total_length = ;

    for (int i = ; i < file_num; i++)

    {

        int file_part_num;

        scanf("%d", &file_part_num);

        total_length += file_part_num;

        for (int j = ; j < file_part_num; j++)

        {

            int original_pos;

            scanf("%d", &original_pos);

            original_pos--;

            link[target_pos] = original_pos;

            target_pos++;

            is_free[original_pos] = false;

        }

    }

}

int drag(int start_point, int end_pos)

{

    optimized = true;

    int next_point;

    while (link[start_point] != end_pos)

    {

        next_point = link[start_point];

        printf("%d %d\n", next_point + , start_point + );

        link[start_point] = -;

        is_free[start_point] = false;

        is_free[next_point] = true;

        start_point = next_point;

    }

    return start_point;

}

void work()

{

    optimized = false;

    for (int i = ; i < total_length; i++)

        if (is_free[i])

            drag(i, -);

    for (int i = ; i < total_length; i++)

    {

        if (link[i] != - && link[i] != i)

        {

            printf("%d %d\n", i + , total_length + );

            is_free[i] = true;

            is_free[total_length - ] = false;

            int last_pos = drag(i, i);

            link[last_pos] = -;

            printf("%d %d\n", total_length + , last_pos + );

            is_free[last_pos] = false;

            is_free[total_length - ] = true;

        }

    }

    if (!optimized)

        printf("No optimization needed\n");

}

int main()

{

    input();

    work();

    return ;

}