题目描述

blablabla

思路

首先存储结构，要根据流量和登机口号两个部分排序，所以想到使用结构体存储
然后对于树形的结构，采用链式存储的方式
根据题意，需要用层次遍历来解决
注意点：增加树结点时需要倒着增加，为了最后层次遍历的顺序

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
const int N = 1010;
int n;
struct port{
    int num;
    int cot;
}p[N];
int h[N],e[N],ne[N],idx;

bool cmp(const port &a,const port &b){
    if(a.cot > b.cot) return true;
    if(a.cot == b.cot) return a.num <= b.num;
    if(a.cot < b.cot) return false;
}

void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

int main(){
    scanf("%d",&n);
    int cnt = 0;
    memset(h,-1,sizeof h);
    int a,b,c,d;
    while(n--){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(d != -1) add(a,d);
        if(c != -1) add(a,c);
        if(b != -1) add(a,b);
    }

    // 判断没有后续输入的结束符
    while(scanf("%d%d",&a,&b) != EOF){
        // 结构体输入方式
        p[cnt] = {a,b};
        cnt++;
    }

    sort(p,p + cnt,cmp);

    // 队列中放的是序号，不是结构体
    queue<int> q;
    // 根节点为100
    q.push(100);

    cnt = 0;
    while(q.size()){
        int u = q.front();
        q.pop();
        for(int i = h[u];i != -1;i = ne[i]){
            int j = e[i];
            if(j >= 100) q.push(j);
            else{
                printf("%d %d\n",p[cnt++].num,j);
            }
        }
    }

    return 0;

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla