hdu1285(拓扑排序+优先队列).MD

日期 2022 / 03 / 22

[参考链接]https://blog.csdn.net/u012860063/article/details/38018811

题目

确定比赛名次

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 10604 Accepted Submission(s): 4150

Problem Description

有N个比赛队（1<=N<=500）。编号依次为1。2，3..N进行比赛，比赛结束后。裁判委员会要将全部參赛队伍从前往后依次排名，但如今裁判委员会不能直接获得每一个队的比赛成绩。仅仅知道每场比赛的结果，即P1赢P2，用P1。P2表示，排名时P1在P2之前。如今请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；当中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1。P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。其它说明：符合条件的排名可能不是唯一的。此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3

1 2

2 3

4 3

Sample Output

1 2 4 3

解题思路

这个题目是个拓扑排序加上优先队列的，我们知道拓扑排序的话我们需要先找到入度为0的点放进队列作为起点，这个题目规定了输出按照字典序，所以我们引进了优先队列，能够自动帮我们 排好序，第二步，我们假定队首元素为a，第二步就是把a的所有邻居点的入度减1，并把入度减为0的点放进队列，这里注意：没有减为0的点不能放进队列，继续操作直至队列为空

代码演示

#include <bits/stdc++.h>

#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 0, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e6 + 10;
using namespace std;

priority_queue <int, vector<int>, greater<int> > q; //升序队列，小顶堆
int map1[517][517];
int cnt[517];
int sum = 1;
int n, m;

void solve() {
  for (int i = 1; i <= n; i++) {
    if (!cnt[i]) {
      q.push(i); // 找到入度为0的点
    }
  }
  sum = 1;
  while (q.size()) {
    int head = q.top();
    q.pop();
    if (sum != n) {
      cout << head << ' ';
      sum++;
    } else {
      cout << head << endl;
    }
    for (int i = 1; i <= n; i++) {
      if (!map1[head][i]) {
        continue;	
      }
      cnt[i]--; //将队首邻近的点的入度减去1
      if (!cnt[i]) {  // 入度为0的点放进队列
        q.push(i);
      }
    }
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int x, y;
  while (cin >> n >> m) {
    format(cnt);
    format(map1);
    for (int i = 0; i < m; i++) {
      cin >> x >> y;
      if (map1[x][y]) {
        continue;
      }
      map1[x][y] = 1;
      cnt[y]++; // 这里相当于记录点的入度
    }
    solve();
  }
  return 0;
}