2016"百度之星" - 初赛（Astar Round2A）1006 Gym Class（HDU5695）—

　　分析：首先，利用贪心可知，如果要所有人的分数和最高，需要把序号大的优先放在前面。其次，对于a的前面不能为b，那么只能a在b前面了，那么就建立一条从a到b的边，并且b的入度加1。然后就是拓扑排序了。要分数最高，则把哪些入度为0的点（他们不需要有哪些人一定要在他们前面，最自由）丢进优先队列，然后就可以实现把序号大的尽量放在前面而且满足题意了。

　　具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <queue>

 using namespace std;

 typedef long long ll;

 vector<int> G[+];

 int in[+],val[+];

 int n,m;

 void solve()

 {

     int sit=;

     priority_queue<int> Q;

     for(int i=;i<=n;i++) if(!in[i]) Q.push(i);

     while(!Q.empty())

     {

         int x=Q.top();Q.pop();

         val[sit++]=x;

         for(int i=;i<G[x].size();i++)

         {

             int v = G[x][i];

             in[v]--;

             if(!in[v]) Q.push(v);

         }

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++) G[i] .clear();

         memset(in,,sizeof(in));

         memset(val,,sizeof(val));

         while(m--)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             G[u].push_back(v);

             in[v]++;

         }

         solve();

         int minn=+;

         ll ans=;

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

         {

             minn=min(minn,val[i]);

             ans+=(ll)minn;

         }

         printf("%I64d\n",ans);

     }

     return ;

 }

巴特西

2016"百度之星" - 初赛（Astar Round2A）1006 Gym Class（HDU5695）——贪心+拓扑排序

最新文章

热门文章