POJ3687 Labeling Balls （拓扑排序）经典

Description

Input

Output

Sample Input

5

4 0

4 1
1 1

4 2
1 2
2 1

4 1
2 1

4 1
3 2

Sample Output

1 2 3 4
-1
-1
2 1 3 4
1 3 2 4

Source

题意：n个重量为1~n的球，给定一些编号间的重量比较关系，现在给每个球编号，在符合条件的前提下使得编号小的球重量小。（先保证1号球最轻，其次2号……）

分析：拓扑排序，注意根据题的要求，要先保证1号球最轻，如果我们由轻的向重的连边，然后我们依次有小到大每次把重量分给一个入度为0的点，那么在拓扑时我们面对多个入度为0的点，我们不知道该把最轻的分给谁才能以最快的速度找到1号（使1号入度为0），并把当前最轻的分给1号。所以我们要由重的向轻的连边，然后从大到小每次把一个重量分给一个入度为0的点。这样我们就不用急于探求最小号。我们只需要一直给最大号附最大值，尽量不给小号赋值，这样自然而然就会把轻的重量留给小号。

#include<stdio.h>
#include<string.h>
const int N = 205;

int mapt[N][N],in[N],w[N],n;
int findroot()
{
    int i,j;
    for( i=n;i>0;i--)
    if(in[i]==0)
    break;
    if(i<=0)
        return 0;
    in[i]=-1;
    return i;
}
int tope()
{
    int a[N],k=0,m=n,s;
    s=findroot();
    while(s)
    {
         w[s]=m; m--;
        for(int i=1;i<=n;i++)
        if(mapt[s][i])
        {
            in[i]-=mapt[s][i];
        }
        s=findroot();
    }
    return m==0;
}
int main()
{
    int t,m,a,b;
    scanf("%d",&t);
    while(t--)
    {
        memset(mapt,0,sizeof(mapt));
        memset(in,0,sizeof(in));

        scanf("%d%d",&n,&m);
        while(m--)
        {
            scanf("%d%d",&a,&b);
            mapt[b][a]++; in[a]++;
        }
        int flag = tope();
        if(flag==0)
        {
            printf("-1\n");
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
               printf("%d",w[i]);
               if(i<n)
                    printf(" ");
            }
            printf("\n");
        }
    }
}