HFUT 1359.吃在工大(安徽省2016“京胜杯”程序设计大赛 F)

397

题目



Description



JH和他的好朋友YZ两名程序员回访母校合工大,准备在这住一段日子,都说“玩在安大,吃在工大”,JH又是一名典型吃货,于是决定在工大食堂好好吃一段日子,但是,面对美食诱惑:黄焖鸡、风暴干锅、麻辣香锅、奥尔良烤翅…由于时间有限,JH不知道哪顿饭吃哪个菜好。
于是YZ为了帮助他解决这个问题,也顺便考考他,给他出了一个问题:“黄焖鸡必须在干锅花菜前面吃,干锅牛肉必须在干锅鱿鱼前面吃….你按这个要求下,就知道吃的顺序啦”。JH抓抓头,分分钟写了个程序搞定,现在,让你来写写看?输出一组JH符合条件下吃的食物的序列。
假设JH每顿只吃一种食物,且每顿吃的都不同,食物编号1到N。


Input



先输入一个整数T,表示T(T<50)组数据。
每组数据第一行输出一个整数,N,M,分别表示有N种食物,总共有M个约束条件,接下来M行每行输入两个正整数a,b(n>=a>0,n>=b>0),表示食物a必须在食物b之前吃。


Output



各组数据输出答案占一行,输出一组符合条件的序列(要求输出字典序最大的那一组),如果答案不存在,输出“-1”。


Sample Input



1
4 3
1 2
2 3
4 3


Sample Output



4 1 2 3


题解



字典序的拓扑排序



普通的拓扑排序没有要求输出字典序最大的解,因此我们可以修改下来做

阅读以下内容,请确保已看过 **>拓扑排序<**

原本的拓扑排序,对于每一个源头,会尽可能将其遍历完再去遍历其他的源。

因此,当存在类似

5 -> 3 -> 1
2 -> 4


的关系时,会先把5当作源头,遍历完再去遍历以2为源的链

5 -> 3 -> 1 -> 2 -> 4


而非我们想要的答案

5 -> 3 -> 2 -> 4 -> 1


我们可以用类似于Dijkstra的形式,维护一个优先队列

当一个点被访问后(记录到结果里后),所有以它为前置元素的元素(删除该点后,所有的源)都可以被访问了。

因此,每次取出优先队列中最大的元素进行拓扑排序,即可获得我们想要的答案。


代码



/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <stack>
#include <map>
using namespace std;

const int maxn = 1000;


bool G[maxn][maxn];

bool vis[maxn];

int n;

bool HasLoop() {
    //判断是否存在环
    for(int i = 1;i <= n;i++)
        if(!vis[i])
            return false;
    return true;
}

bool IsStart(int k) {
    //判断是否入度为0
    for(int i = 1;i <= n;i++)
        if(G[i][k])
            return false;
    return true;
}


bool TopoSort(int _n,int *ans) {
    //拓扑排序
    /*
    参数:
    邻接矩阵G[][]
    顶点数目n
    用于保存拓扑排序结果的数组 ans[]
    */
    //输出结果下标初始化
    int pos = 0;

    //已访问数组初始化
    memset(vis,false,sizeof(vis));

    //可被选择的数
    priority_queue<int> Q;

    //判断i是否为源
    for(int i = 1;i <= n;i++) {
        if(IsStart(i))
            Q.push(i);
    }

    while(!Q.empty()) {
        int k = Q.top();
        Q.pop();

        if(vis[k])
            continue;
        else
            vis[k] = true;

        //记录到结果中
        ans[pos++] = k;

        for(int i = 1;i <= n;i++) {
            if(G[k][i]) {
                //路径k~i存在
                //删除路径
                G[k][i] = false;
                //如果成为入度为0的点
                if(IsStart(i))
                    Q.push(i);
            }
        }
    }

    //判断是否有环
    return HasLoop();
}



void Do() {
    memset(G,0,sizeof(G));
    int m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < m;i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a][b] = 1;
    }

    int ans[maxn];
    if(TopoSort(n,ans)) {
        for(int i = 0;i < n;i++) {
            if(i)
                printf(" ");
            printf("%d",ans[i]);
        }
    } else {
        printf("-1");
    }
    printf("\n");

}

int main() {
    int T;
    scanf("%d",&T);
    while(T--)
        Do();
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论