11112: 【原1112】二哥发论文

题目

题目描述

author: Cheng Chen 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1112

Description

二哥是一个热爱科研的人。前几天二哥的一篇论文被某个国际顶级会议录用，今天，二哥要在学校里举行一个学术问答会，接受同学们的提问。

在交大，有n个人对二哥的研究方向感兴趣（以1-n编号）.他们并不互相认识，但是如果甲认识乙那么乙一定认识甲. 这n个人中有k个人得知二哥要举行问答会。二哥并不是随便接受提问的，他会在排队提问的人当中挑选学术水平最高的人接受提问。而提问完之后，这位同学会立刻去找他认识的并对二哥的研究方向感兴趣的人，而这些人也会第一时间赶到现场排队提问。现在二哥想知道提问的同学是按什么顺序提问的。

Input Format

第一行包含了两个整数n,k(k<=n<=1000). 接下来一行有n个整数，表示每个同学的学术水平（<=100000).每个同学的学术水平各不相同. 接下来一行有k个整数，表示一开始就知道二哥的讲座的同学的标号(从1开始). 最后是一个n*n的矩阵，若第i行第j列是1则表示标号为i的同学和标号为j的同学认识，否则为不认识。

Output Format

每行一个整数，按顺序表示提问的同学的编号.

Sample Input

5 2
76708 24510 69869 85113 61546
3 4
0 1 1 1 1
1 0 1 0 1
1 1 0 0 0
1 0 0 0 0
1 1 0 0 0

Sample Output

4
1
3
5
2

FineArtz's solution

/* 二哥发论文 */
#include <iostream>
using namespace std;

class Heap{
private:
    int a[1005] = {0};
    int b[1005] = {0};
    int heapsize = 0;

    void swap(int x, int y){
        int t = a[x];
        a[x] = a[y];
        a[y] = t;
        t = b[x];
        b[x] = b[y];
        b[y] = t;
    }

public:
    void siftup(int i){
        while (i != 1){
            if (a[i] > a[i / 2]){
                swap(i, i / 2);
                i /= 2;
            }
            else
                break;
        }
    }

    void siftdown(){
        int i = 2;
        while (i <= heapsize){
            if (i + 1 <= heapsize && a[i] < a[i + 1])
                ++i;
            if (a[i] > a[i / 2]){
                swap(i, i / 2);
                i *= 2;
            }
            else
                break;
        }
    }

    void insert(int x, int y){
        a[++heapsize] = x;
        b[heapsize] = y;
        siftup(heapsize);
    }

    void remove(){
        swap(1, heapsize);
        --heapsize;
        siftdown();
    }

    int getMax(){
        return b[1];
    }

    bool empty(){
        return (heapsize == 0);
    }
};

Heap heap;
int n, k;
int a[1005], m[1005][1005];
bool v[1005] = {false};

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    for (int i = 1; i <= k; ++i){
        int t;
        cin >> t;
        heap.insert(a[t], t);
        v[t] = true;
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= n; ++j){
            cin >> m[i][j];
        }
    }
    while (!heap.empty()){
        int x = heap.getMax();
        cout << x << endl;
        heap.remove();
        for (int i = 1; i <= n; ++i)
            if (m[x][i] && !v[i]){
                heap.insert(a[i], i);
                v[i] = true;
            }
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstring"
using namespace std;

template <class T>
class mVector {
    T** vector_data = nullptr;
    unsigned int size = 0;
    unsigned int capacity = 0;

public:
    //构造函数
    mVector() = default;
    mVector(unsigned int _size) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
    }
    mVector(unsigned int _size, const T& val) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
        for (unsigned int i = 0; i < _size; ++i)
            vector_data[i] = new T(val);
    }
    mVector(const mVector<T>& _vector) :size(_vector.size), capacity(_vector.capacity) {
        vector_data = new T * [capacity] {nullptr};
        for (int i = 0; i < size; ++i)
            vector_data[i] = new T(*_vector.vector_data[i]);
    }
    //析构函数
    ~mVector() {
        for (unsigned int i = 0; i < size; ++i)
            delete vector_data[i];
        delete[] vector_data;
    }

    //迭代器
    class iterator {
        T** pos = nullptr;
        friend iterator mVector<T>::begin();
        friend iterator mVector<T>::end();
        friend void mVector<T>::erase(const iterator& val);
    public:
        iterator() = default;
        iterator(const iterator& other) {
            pos = other.pos;
        }
        iterator& operator++() {
            ++pos;
            return *this;
        }
        iterator operator++(int) {
            iterator temp(*this);
            ++pos;
            return temp;
        }
        iterator& operator--() {
            --pos;
            return *this;
        }
        iterator operator--(int) {
            iterator temp(*this);
            --pos;
            return temp;
        }
        bool operator==(const iterator& other) const {
            return pos == other.pos;
        }
        bool operator!=(const iterator& other) const {
            return pos != other.pos;
        }
        iterator& operator=(const iterator& other) {
            pos = other.pos;
            return *this;
        }
        T& operator*() const {
            return **pos;
        }
    };

    //增加元素
    void push_back(const T& val) {
        if (size < capacity)
            vector_data[size++] = new T(val);
        else {
            T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
            for (unsigned int i = 0; i < size; ++i)
                temp_data[i] = vector_data[i];
            temp_data[size++] = new T(val);
            capacity = (capacity + 1) * 2;
            delete[] vector_data;
            vector_data = temp_data;
        }
    }

    //删除末尾
    void pop_back() {
        delete vector_data[--size];
        vector_data[size] = nullptr;
    }

    //清空
    void clear() {
        for (unsigned int i = 0; i < size; ++i) {
            delete vector_data[i];
            vector_data[i] = nullptr;
        }
        size = 0;
    }

    //删除
    void erase(const iterator& val) {
        delete* val.pos;
        for (auto p = val.pos; p != vector_data + size - 1; ++p)
            * p = *(p + 1);
        --size;
        vector_data[size] = nullptr;
    }

    //重载运算符
    T& operator[](const unsigned int& pos) {
        return *vector_data[pos];
    }

    iterator begin() {
        iterator temp;
        temp.pos = vector_data;
        return temp;
    }

    iterator end() {
        iterator temp;
        temp.pos = vector_data + size;
        return temp;
    }

};

template <class T>
class myPriorityQueue {
    mVector<T> queueData;
    unsigned int sizeOfQueue = 0;
    bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

    //向下过滤
    void percolateDown(unsigned int pos) {
        while (pos * 2 <= sizeOfQueue) {
            if (pos * 2 + 1 > sizeOfQueue) {
                //交换
                if (cmp(queueData[pos * 2], queueData[pos])) {
                    auto temp = queueData[pos * 2];
                    queueData[pos * 2] = queueData[pos];
                    queueData[pos] = temp;
                }
                break;
            }
            else {
                bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
                if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
                    auto temp = queueData[pos * 2 + minNum];
                    queueData[pos * 2 + minNum] = queueData[pos];
                    queueData[pos] = temp;
                    pos = pos * 2 + minNum;
                }
                else break;
            }
        }
    }

public:
    //构建
    myPriorityQueue() {
        queueData.clear();
        queueData.push_back(*new T);
        sizeOfQueue = 0;
    }

    //compare函数返回父结点a与孩子结点b的关系正确与否
    myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
        queueData.clear();
        queueData.push_back(*new T);
        sizeOfQueue = 0;
    }

    //根据数组建立堆
    void buildHeap(T* eleData, unsigned int eleNum) {
        queueData.clear();
        sizeOfQueue = eleNum;
        queueData.push_back(*new T);
        for (unsigned int i = 1; i <= eleNum; i++)
            queueData.push_back(eleData[i - 1]);
        //向下过滤
        for (unsigned int pos = eleNum / 2; pos > 0; pos--)
            percolateDown(pos);
    }

    //判断是否空
    bool empty() {
        return sizeOfQueue == 0;
    }

    //返回队列大小
    auto size() {
        return sizeOfQueue;
    }

    //入队
    void push(const T& input) {
        sizeOfQueue++;
        queueData.push_back(input);

        //向上过滤
        for (auto i = sizeOfQueue; i > 1; i = i / 2) {
            //判断是否比父结点更小
            if (cmp(queueData[i], queueData[i / 2])) {
                //交换
                auto temp = queueData[i];
                queueData[i] = queueData[i / 2];
                queueData[i / 2] = temp;
            }
            else break;
        }
    }

    //队列最前
    T top() {
        return queueData[1];
    }

    //出队
    T pop() {
        auto temp = queueData[1];
        queueData[1] = queueData[sizeOfQueue--];
        queueData.pop_back();
        percolateDown(1);
        return temp;
    }
};

class student {
public:
    int code = 0;
    int val = 0;
};

bool map_data[1009][1009] = { 0 };
student val_data[1009];
bool visited[1009] = { 0 };

myPriorityQueue<student> queue_data([](student a, student b) {return a.val > b.val; });

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        val_data[i].code = i;
        cin >> val_data[i].val;
    }

    for (int i = 0; i < k; ++i) {
        int temp;
        cin >> temp;
        visited[temp - 1] = true;
        queue_data.push(val_data[temp - 1]);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> map_data[i][j];
        }
    }

    while (!queue_data.empty()) {
        auto temp = queue_data.top();
        queue_data.pop();
        cout << temp.code + 1 << " ";
        for (int i = 0; i < n; ++i) {
            if (map_data[temp.code][i] && !visited[i]) {
                queue_data.push(val_data[i]);
                visited[i] = true;
            }
        }
    }

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

struct student {
    int num;
    int knowledge;

    bool operator<(const student &right) const {
        return knowledge < right.knowledge;
    }
};

const int maxN = 1e3 + 10;

int interest[maxN] = {0}, n, k;
bool rec[maxN][maxN] = {0}, inque[maxN] = {0};
student stu[maxN] = {0};

template <class Type>
class priorityQueue {
   private:
    int currentSize;
    Type *array;
    int maxSize;

    void doubleSpace();
    void buildHeap();
    void percolateDown(int);

   public:
    priorityQueue(int capacity = maxN);
    priorityQueue(const Type *data, int size);
    ~priorityQueue();
    bool isEmpty() const;
    void enQueue(const Type &x);
    Type deQueue();
    Type getHead() const;
};

template <class Type>
priorityQueue<Type>::priorityQueue(int capacity)
    : maxSize(capacity), currentSize(0) {
    array = new Type[capacity];
}

template <class Type>
priorityQueue<Type>::priorityQueue(const Type *data, int size)
    : maxSize(size + 10), currentSize(size) {
    array = new Type[maxSize];

    for (int i = 0; i < size; i++) {
        array[i + 1] = data[i];
    }

    buildHeap();
}

template <class Type>
priorityQueue<Type>::~priorityQueue() {
    delete[] array;
}

template <class Type>
bool priorityQueue<Type>::isEmpty() const {
    return currentSize == 0;
}

template <class Type>
Type priorityQueue<Type>::getHead() const {
    return array[1];
}

template <class Type>
void priorityQueue<Type>::enQueue(const Type &x) {
    if (currentSize == maxSize - 1) {
        // doubleSpace();
    }

    int hole = ++currentSize;
    for (; hole > 1 && x < array[hole / 2]; hole /= 2) {
        array[hole] = array[hole / 2];
    }

    array[hole] = x;
}

template <class Type>
Type priorityQueue<Type>::deQueue() {
    Type minItem;

    minItem = array[1];
    array[1] = array[currentSize--];
    percolateDown(1);

    return minItem;
}

template <class Type>
void priorityQueue<Type>::percolateDown(int hole) {
    int child;
    Type tmp = array[hole];

    for (; hole * 2 <= currentSize; hole = child) {
        child = hole * 2;

        if (child != currentSize && array[child + 1] < array[child]) {
            child++;
        }

        if (array[child] < tmp) {
            array[hole] = array[child];
        } else {
            break;
        }
    }
    array[hole] = tmp;
}

template <class Type>
void priorityQueue<Type>::doubleSpace() {
    Type *tmp = array;

    maxSize *= 2;

    array = new Type[maxSize];
    for (int i = 0; i < currentSize; i++) {
        array[i] = tmp[i];
    }

    delete[] tmp;
}

template <class Type>
void priorityQueue<Type>::buildHeap() {
    for (int i = currentSize / 2; i > 0; i--) {
        percolateDown(i);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    priorityQueue<student> que;

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        stu[i].num = i;
        cin >> stu[i].knowledge;
        stu[i].knowledge = -stu[i].knowledge;
    }
    for (int i = 0; i < k; i++) {
        int temp;
        cin >> temp;
        que.enQueue(stu[temp]);
        inque[temp] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> rec[i][j];
        }
    }

    while (!que.isEmpty()) {
        int temp = que.deQueue().num;
        cout << temp << '\n';

        for (int i = 1; i <= n; i++) {
            if (!inque[i] && rec[temp][i]) {
                que.enQueue(stu[i]);
                inque[i] = 1;
            }
        }
    }

    return 0;
}

yyong119's solution

#include <cstdio>
#include <queue>
using namespace std;

int index[100005], relation[1005][1005], level[1005];
bool known[1005];
priority_queue<int> pri_que;

int main() {

    int n, k; scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &level[i]);//level[i]第i个人的知识水平
        index[level[i]] = i;//知识水平为level[i]的人的编号
    }
    for (int i = 1; i <= k; ++i) {
        int id; scanf("%d", &id);
        known[id] = true; pri_que.push(level[id]);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &relation[i][j]);

    while (!pri_que.empty()) {
        int asked_index = index[pri_que.top()];
        printf("%d\n", asked_index);
        pri_que.pop();
        for (int i = 1; i <= n; ++i)
            if (relation[i][asked_index] && !known[i]) {
                pri_que.push(level[i]);
                known[i] = true;
            }
    }

    return 0;
}