学步园

题目链接：点击打开链接

很给力的道题，拓扑排序的应用，算是对TopSort认识更深了吧。

拓扑排序这里不做过多的解释，主要来说这道题的应用。

题目的意思就是给1——N质量的N个球贴标签，要求就是满足要求下的标签小的尽量轻。

没什么深入想，直接TopSort。果断WA，WA的。后来看题，发现了很多的问题。输出的是Label1-LabelN标签的重量。还有很多的问题没有看太清晰。

再看了几遍题意后，还是WA WA的。果断不知道怎么弄了。

拿来一组数据比较了一下，果断ANSWER是错误的。

后来我都有点混乱了。

我可以有两种操作：

一，我找到满足条件的质量最小的一次贴标签。

二，我还是找到满足条件的最小的标签给质量依次贴。

权衡操作复杂度来看，第一种比较简单。

上WA的代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int N=205;
bool vis[N];
int n,m,Enter[N];
vector<int> map[N];

void TopSort(){
    int q[N],top=1;
    while(1){
        int cnt=0,p;
        for(int i=n;i>=1;i--)
        if(Enter[i]==0&&!vis[i]){
            cnt++;p=i;
        }
        if(cnt==0) break;
        else q[p]=top++;
        for(int i=0;i<map[p].size();i++)
        Enter[map[p][i]]--;
        vis[p]=true;
    }
    if(top-1==n){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=top;j++)
            if(q[j]==i) printf("%d ",j);
        }
    }
    else printf("-1");
    printf("\n");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        CLR(vis,0);CLR(Enter,0);CLR(map,0);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            map[a].push_back(b);
            Enter[b]++;
        }
        TopSort();
    }
    return 0;
}

比如这组数据

5 4

1 4

4 2

5 3

3 2

错误的程序错误输出为：

1 4 5 3 2

通过手模拟我们可以知道：

1 5 3 4 2

这是为什么呢？？？

因为，单入度为0的节点有多个的时候 ，我们选择的标准应该是什么？

有很多的朋友肯定会说当然是选择质量最小的啊。对，我也是这么想的。

但是，如果这样做的话，就会出现，后面出现更小的质量同样也满足条件。

比如 假设 1 3 5 4 2 和 1 5 3 4 2这两种， 条件同样满足。但是5先出现了入度为0 的情况。这样就不对了。

经过百度加上自己的理解，学会了普遍的反向建图的方法。

正确代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;

const int N=205;
bool vis[N];
int n,m,Enter[N];
bool map[N][N];

void TopSort(){
    int q[N],top=n;
    while(top>0){
        int cnt=0,p;
        for(int i=1;i<=n;i++)
        if(Enter[i]==0&&!vis[i]){
            cnt++;p=i;
        }
        //面对多个入度为0的节点时，我们该怎么处理？
        //是 将小的节点进入序列 删边 再重新选点
        //还是 将所有的节点进入序列 删边 再选点？
        if(cnt==0) break;
        else q[top--]=p;

        for(int i=1;i<=n;i++)
        if(map[p][i]) Enter[i]--;
        vis[p]=true;
    }
    if(top==0){
        //这里明显是找到合适的标签贴到ball上.
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)
            if(q[j]==i) printf("%d%c",j,i==n?'\n':' ');
        }
    }
    else printf("-1\n");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        CLR(vis,0);CLR(Enter,0);CLR(map,0);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            if(!map[b][a]){
                map[b][a]=true;
                Enter[a]++;
            }
        }
        TopSort();
    }
    return 0;
}

反向建图，找最大的标签给最大质量的ball贴。
这里吧第一种操作和第二种操作搞晕了。

如果你是第一种操作那么相当于把标签的顺序已经排好（1-n），需要挑选合适质量的球。

第二种，反之。

好题。！