poj 3687 拓扑排序

题意：求一个拓扑排序，使其weight是递增的，当有多个序列存在是，要求首先使1号的weight最小，然后是2号....

解题思路：

对于一个有向无环图，若按质量轻的往质量大的建边，那么当有多个入度为0的点存在时，不能确定将哪个放在前面能使其最终序列最优，但反过来思考，

对于出度为0的所有点，其中编号最大的让其排到最后面，那么结果一定是最优的。

#include<iostream>
#include<cstdio>
#include<cstring>
#define Maxn 402
#define Maxm 40010
using namespace std;
int graphic[Maxn][Maxn],indegree[Maxn],n,m,ans[Maxn],label;
int Topsort()
{
    int i,j,k,num=0;
    for(i=1;i<=n;i++)
    {
        for(j=n;j>=1;j--)
        {
            if(indegree[j]==0)
            {
                indegree[j]--;
                ans[j]=label--;
                for(k=1;k<=n;k++)
                    if(graphic[j][k])
                        indegree[k]--;
                num++;
                break;
            }
        }
    }
    if(num<n)
        return 0;
    return 1;
}
int main()
{
    int t,i,j,a,b;
    scanf("%d",&t);
    while(t--)
    {
        memset(indegree,0,sizeof(indegree));
        memset(graphic,0,sizeof(graphic));
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            if(!graphic[b][a])
                indegree[a]++,graphic[b][a]=1;
        }
        label=n;
        if(Topsort())
        {
            for(i=1;i<n;i++)
                printf("%d ",ans[i]);
            printf("%d
",ans[i]);
        }
        else
            printf("-1
");
    }
    return 0;
}