NOIP 2009 最优贸易解题报告

　　这题我纠结了三天，今天终于AC了，，辛苦死我了。。
　　这题我看错了题目，连续两次。最后才弄清楚题目，就是两次搜索，第一次搜索所有的最小的价格，第二次搜索所有的最大的价格，然后就是枚举每一个节点的最大值-最小值。
　　其中的数据结构是我偶然想到的，直接用一个数组表示，然后用另外一个数组进行标识每个都是哪个的邻接。
　　思路真的没说清楚，我不想再说了，这题太难了（算法不难，空间压缩难。）。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100001
#define minnum(a, b) ((a)<(b)?(a):(b))
#define maxnum(a, b) ((a)>(b)?(a):(b))
struct place{
int x, y;
}map[1000000];
int inv[1000000], outv[1000000];
/* 表示所有的的节点的入节点和出节点 */
int len;
int in[1000000], out[1000000];
/* in[0] ~ in[1] 代表进节点1的的inv的下标. */
//上面的数组第一次都开小了,
int money[MAX];
int max[MAX], min[MAX];
int at[MAX];
int n, m;
int queue[MAX];
int h, q;

void enqueue(int x)
{
        int t;
        t = q + 1;
        if(t > MAX){
                t = 0;
        }
        if(t == h){
                exit(-1);
        }
        queue[q] = x;
        q = t;
}

int exqueue(void)
{
        int t, r;
        if(h == q){
                exit(-1);
        }

        t = h + 1;
        if(t > MAX){
                t = 0;
        }
        r = queue[h];
        h = t;
        return r;

}

void add(int i, int j)
{
        map[len].x = i;
        map[len].y = j;
        in[j]++;
        out[i]++;
        len++;
}

int com1(const void *a, const void *b)
{
struct place i = *(struct place *)a, j = *(struct place *)b;
return i.x – j.x;
}

int com2(const void *a, const void *b)
{
struct place i = *(struct place *)a, j = *(struct place *)b;
return i.y – j.y;
}

void sort(int *a)
{
        int t = 0, r;
        int i;
        for(i = 1; i <= n; i++){
                r = a[i];
                a[i] += t;
                t += r;
        }
}

int main(void)
{
        int i, j;
        int a, b, c;
        int t, ans;
        scanf(“%d%d“, &n, &m);
        for(i = 1; i <= n; i++){
                scanf(“%d“, &money[i]);
        }
        for(i = 1; i <= m; i++){
                scanf(“%d%d%d“, &a, &b, &c);
                add(a, b);
                if(c == 2){
                        add(b, a);
                }
        }
        qsort(map, len, sizeof(struct place), com1);           //对inv和outv赋值
        for(i = 0; i < len; i++){
                outv[i] = map[i].y;
        }
        qsort(map, len, sizeof(struct place), com2);
        for(i = 0; i < len; i++){
                inv[i] = map[i].x;
        }
        sort(in);                                               //对下标赋值
        sort(out);

        for(i = 1; i <= n; i++){
                min[i] = 1000000;
                max[i] = 0;
        }

        enqueue(1); at[1] = 1;                         //搜索所有价格中最低的
        while(h != q){
                t = exqueue();
                at[t] = 0;
                for(i = out[t – 1]; i < out[t]; i++){
                        j = outv[i];
                        if(min[j] > min[t] || money[j] < min[j]){
                                min[j] = minnum(money[j], min[t]);
                                if(!at[j]){
                                        at[j] = 1;
                                        enqueue(j);
                                }
                        }
                }
        }
        enqueue(n); at[n] = 1;                         //搜索所有价格中最高的
        while(h != q){
                t = exqueue();
                at[t] = 0;
                for(i = in[t – 1]; i < in[t]; i++){
                        j = inv[i];
                        if(max[j] < max[t] || money[j] > max[j]){
                                max[j] = maxnum(money[j], max[t]);
                                if(!at[j]){
                                        at[j] = 1;
                                        enqueue(j);
                                }
                        }
                }
        }

        ans = 0;
        for(i = 1; i <= n; i++){
                if(max[i] – min[i] > ans){
                        ans = max[i] – min[i];
                }
        }

printf(“%d\n“, ans);
return 0;
}

NOIP 2009 最优贸易 解题报告

推荐文章：

发表回复 取消回复

NOIP 2009 最优贸易解题报告

发表回复取消回复