# 11112: 【原1112】二哥发论文

### 题目描述

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

## 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();
};

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>
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()) {