poj 3687 Labeling Balls(拓扑排序)

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

然后，按照重量1~n的输出位置

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

 #include <iostream>

  #include<cstdio>

  #include<cstring>

  #include<cstdlib>

  #include<stack>

  #include<queue>

  #include<iomanip>

  #include<cmath>

  #include<algorithm>

  using namespace std;

  int main()

  {

      int t,i,j,n,m,u,v,k,f;

      int r[],G[][],a[];

      cin>>t;

      while(t--)

      {

          k=;

          f=;

          cin>>n>>m;

          memset(r,,sizeof(r));

          memset(G,,sizeof(G));

          while(m--)

          {

              cin>>u>>v;

              if(!G[v][u])

              {

                  G[v][u] = ;   //反向建图

                  r[u]++;

              }

          }

          for(i = n; i >= ; i--) // 代表位置，倒序找最大的

          {

              for(j = n; j >= ; j--) //代表球的重量，倒序找球的重量最大的

              {

                  if(!r[j])  //从最后开找

                  {

                      a[j]=i;

                      r[j]--;

                      for(k = ; k <= n; k++)

                          if(G[j][k])

                              r[k]--;

                      break;

                  }

              }

              if(j==)

              {

                  f=;

                  break;

              }

          }

          if(f) cout<<"-1"<<endl;

          else

          {

              for(i=; i<n; i++)

                  printf("%d ",a[i]);

              if(n>=)

                  printf("%d\n",a[i]);

          }

      }

      return ;

  }

巴特西

poj 3687 Labeling Balls(拓扑排序)

最新文章

热门文章