跳至正文

Noip 2010 提高组 第三题 关押罪犯

  • OI路程

  这题的话,就是贪心,把最大的罪恶值的两个囚犯都不关在一个牢房里,反复的贪心,但是数据太大,不允许使用邻接表和邻接矩阵,用什么结构来保存呢?我觉得(也是网上的资料里的咯)使用动态分配是个方法,因为最多10000条边,根据实际情况来分配,这样不会有浪费的空间,也就不会导致空间爆掉了。

#include <stdio.h>
#include <stdlib.h>
int m, n;
struct list{
        int a, b, v;
}list[100001];
struct link{
        int b;
        struct link next;
}head[20000];
int color[20000];
int nowco = 1;

int com(const void a, const void b)
{
        return ((struct list
)b)->v – ((struct list)a)->v;
}

void add(int a, int b)
{
        struct link
p;
        p = malloc(sizeof(struct link));
        p->b = b;
        p->next = head[a].next;
        head[a].next = p;
}

int other_color(int c)
{
        if(c & 1){
                return c + 1;
        }
        return c – 1;
}

int min(int a, int b)
{
        return a > b ? b : a;
}

void dfs(int a)
{
        struct link i;
        for(i = head[a].next; i != NULL; i = i->next){
                if((color[i->b] – color[a] >= –1) && (color[i->b] – color[a] <= 1) && 
                        (min(color[i->b], color[a]) & 1)){
                        continue;
                }
                color[i->b] = other_color(color[a]);
                dfs(i->b);
        }
}

#define d(a) #a

int main(void)
{
        int i, j;
        struct link
p;
        int a, b;
        freopen("prison"d(5)".in""r"stdin);
        scanf("%d%d", &n, &m);
        for(i = 0; i < m; i++){
                scanf("%d%d%d", &list[i].a, &list[i].b, &list[i].v);
                list[i].a–, list[i].b–;
        }
        qsort(list, m, sizeof(struct list), com);
        for(i = 0; i < m; i++){
                a = list[i].a;
                b = list[i].b;
                add(a, b);
                add(b, a);
                if(color[a] == 0 || color[b] == 0){
                        color[a] = nowco++;
                        color[b] = nowco++;
                        continue;
                }else if(color[a] == 0){
                        color[b] = other_color(color[a]);
                        continue;
                }else if(color[b] == 0){
                        color[a] = other_color(color[b]);
                        continue;
                }
                if(color[a] == color[b]){
                        break;
                }
                dfs(b);
        }
        printf("%d\n", list[i].v);
        getch();
        return 0;
}

发表回复

您的电子邮箱地址不会被公开。