HDU 5813 Elegant Construction ——（拓扑排序，构造）

　　可以直接见这个博客：http://blog.csdn.net/black_miracle/article/details/52164974。

　　对其中的几点作一些解释：

　　1.这个方法我们对队列中取出的元素，把仍有出度的点连接到这个点时，这个点是不会连接到多余的点的，因为：一个点出队列的时候其他没入队的点都已经连接到这个点过了，后来再一个点出队列的时候，我们拿此时没入队的点连接到它时，肯定已经连接过之前的点了，所以肯定不会增加到达的点数。（可能我也用语言讲不太清楚233。。。）

　　2.为什么这个人的博客说最终如果num不是0的话就表示成环了？理由如下：不妨考虑四个点的情况：3，3，3，0。最后一个点操作后，出度变为2，2，2，0。这个时候队列已经空了，然而num还不是0，说明还有点没有完成达到它所需要达到的点数（也可以这么解释：num的个数表示还没有完成点数个数任务的点的个数，num=0才表示所有的点都已经完成到达点数个数的目标了，不是0当然不能够满足题意了）。至于为什么是成环的话，因为它们不能够完成点数个数任务，所以他们必须连向别人构成环来构成目标了呗~

　　反正这个拓扑排序有点奥义，需要好好理解~

　　代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <set>

 #include <queue>

 using namespace std;

 const int N =  + ;

 struct edge

 {

     int u,v;

     bool operator < (const edge &temp) const

     {

         return u == temp.u ? v<temp.v : u<temp.u;

     }

 };

 int a[N],inq[N],n;

 set<edge> S;

 void solve()

 {

     queue<int> Q;

     int cnt = n;

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

     {

         if(!a[i])

         {

             Q.push(i);

             inq[i] = ;

             cnt--;

         }

     }

     while(!Q.empty())

     {

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

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

         {

             if(!inq[i])

             {

                 a[i]--;

                 S.insert((edge){i,x});

                 if(!a[i])

                 {

                     Q.push(i);

                     inq[i] = ;

                     cnt--;

                 }

             }

         }

     }

     if(cnt) puts("No");

     else

     {

         puts("Yes");

         printf("%d\n",S.size());

         for(set<edge>::iterator it=S.begin();it!=S.end();it++)

         {

             edge e = *it;

             printf("%d %d\n",e.u,e.v);

         }

     }

 }

 int main()

 {

     int T;scanf("%d",&T);

     for(int kase=;kase<=T;kase++)

     {

         scanf("%d",&n);

         S.clear();memset(inq,,sizeof(inq));

         for(int i=;i<=n;i++) scanf("%d",a+i);

         printf("Case #%d: ",kase);

         solve();

     }

     return ;

 }

巴特西

HDU 5813 Elegant Construction ——（拓扑排序，构造）

最新文章

热门文章