`
lovnet
  • 浏览: 6670707 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

HDU 1811 Rank of Tetris(拓扑排序+并查集)

 
阅读更多

题目链接:Click here~~

题意:

中文题啊中文题。

解题思路:

此题关键的一点是要意识到排序时,Rating相同的人一定排列在一起,且顺序一定存在。

故可以用并查集先将数据中Rating相同的人看做一个集合,然后将各个集合拓扑排序。

接下来就是对于拓扑排序的理解了,当找不到入度为0的点时,图中有环,故会出现冲突。

当每次找到入度为0的点大于1个的时候,说明有多种排序方式,即信息不全。

ps:做完这道题,对拓扑排序的理解又加深了些,话说又不小心进rank了,哎,这rp。

#include <queue>
#include <stdio.h>
#include <string.h>

using namespace std;

#define N 10005

#define FileIn  freopen("in.ads","r",stdin)
#define FileOut freopen("Wa.ads","w",stdout)

struct T
{
    int v,next;
}E[N+N];

struct TT
{
    int head,rd;
}V[N];

int top,ans,cnt,n,m;

int pre[N];

bool Uncertain;

int Root(int x)
{
    if(pre[x] == -1)
        return x;
    else
        pre[x] = Root(pre[x]);
}

void Add_Edge(int u,int v)
{
    E[top].v = v;
    E[top].next = V[u].head;
    V[u].head = top++;
    ++V[v].rd;
}

bool Top_Sort()
{
    queue<int> Q;
    Uncertain = false;
    for(int i=1;i<=n;i++)
        if(V[i].rd == 0 && i == Root(i))    //the key
            Q.push(i);
    while(!Q.empty())
    {
        ++cnt;
        if(Q.size() > 1)                    //the details
            Uncertain = true;
        int p = Q.front();
        //printf("p->%d\n",p-1);
        for(int i=V[p].head;i!=NULL;i=E[i].next)
        {
            int q = E[i].v;
            if(--V[q].rd == 0)
                Q.push(q);
        }
        Q.pop();
    }
    return cnt == n;
}
int main()
{
    //FileIn;FileOut;
    int u[N],v[N];
    char c[N];
    while(~scanf("%d%d",&n,&m))
    {
        memset(V,0,sizeof(V));
        memset(pre,-1,sizeof(pre));
        top = 1; ans = cnt = 0;
        Uncertain = false;
        for(int i=0;i<m;i++)
        {
            scanf("%d %c %d",&u[i],&c[i],&v[i]);
            ++u[i],++v[i];
            if(c[i] == '=')
            {
                int r1 = Root(u[i]);
                int r2 = Root(v[i]);
                //printf("r1->%d,r2->%d\n",r1,r2);
                if(r1 != r2)
                {
                    pre[r1] = r2;
                    ++cnt;
                }
            }
        }
        for(int i=0;i<m;i++)
        {
            int r1 = Root(u[i]);
            int r2 = Root(v[i]);
            //printf("%d's ->r1->%d  ,%d's  ->r2->%d\n",u[i]-1,r1-1,v[i]-1,r2-1);
            switch(c[i])
            {
                case '>':
                    if(r1 == r2)
                        goto end;
                    else
                        Add_Edge(r1,r2);
                    break;
                case '<':
                    if(r1 == r2)
                        goto end;
                    else
                        Add_Edge(r2,r1);
                    break;
            }
        }
        if(!Top_Sort())
end:        puts("CONFLICT");
        else
            puts(Uncertain ? "UNCERTAIN" : "OK");
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics