跳至正文

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;
}

发表回复

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