[Kattis] Chess Tournament 题目分析

2020年3月8日 malic Comments 0 Comment

题面：

棋牌锦标赛中,有N名选手（编号从0到N-1）参与到M场比赛中。这种棋的运气成分影响非常小，如果棋手的技术水平更高，他就能击败对手。只有两个玩家的棋力相同时，这一盘棋才会平局。
只要所有选手都发挥稳定，比赛结果就会符合预期。但是有些棋手会在比赛过程中出现心理或情绪上的波动而导致可能高手输给菜鸟，或者原本棋力相当的两人应当“和棋”却分出了胜负等等情况。
给出这N名选手在M场比赛的战绩，请分析这一组选手是否都是水平稳定的（比赛结果之间不矛盾）。若所有选手都水平稳定，则输出”consistent”，若棋局战绩的前后有矛盾，则输出”inconsistent”

https://open.kattis.com/problems/chesstournament

分析：

所有棋力水平相同的都视作同一个结点，再检查各不同的结点之间是否“矛盾”。
可以将所有数据全存下，遍历第1遍建立并查集，将所有相等的放在同一集合中。遍历第2遍建立有向图，属于同一集合的就认为是同一个结点。为了方便可以对结点重新编号
所谓”出现矛盾”可以解释成有向图当中存在环（包括自己指向自己的情况，当然这种情况也可以提前由并查集确定）。最后只需要检查此有向图是否存在回路（不断删去入度为0的点和所对的边，直到不存在入度为0的点，若图还剩结点则存在回路），若存在回路则可以下结论为矛盾的。

完整程序既要实现集合的方法，又要包含有向图的方法，阅读起来可能比较困难。set_开头的函数表示是集合的方法，graph_开头的表示是图的方法。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXM 250002
#define MAXN 50002
#include <vector>
using std::vector;
#include <queue>
using std::queue;
#include <map>
using std::map;
struct Node
{
    int u,v;
    char op;
} node[MAXM];
vector<int> G[MAXN];
int in_degree[MAXN];
map<int,int> vertexIdMap;
int num_vertex=0;
void graph_add_edge(int u,int v)
{
    G[v].push_back(u);
    in_degree[u]+=1;
}
int graph_vertexID(int v)
{
    if(vertexIdMap.count(v))
    {
        return vertexIdMap[v];
    }
    else
    {
        vertexIdMap[v] = num_vertex ;
        num_vertex +=1;
        return vertexIdMap[v];
    }
}
int set_parent[MAXN];
int set_findParent(int u);
void set_union(int u,int v)
{
    int x = set_findParent(u);
    int y = set_findParent(v);
    if(x!=y)
    {
        if(set_parent[x] < set_parent[y])
        {
            set_parent[x] += set_parent[y];
            set_parent[y] = x;
        }
        else
        {
            set_parent[y] += set_parent[x];
            set_parent[x] = y;
        }
    }
}
int set_findParent(int u)
{
    if(set_parent[u]<0)
        return u;
    else
    {
        set_parent[u] = set_findParent(set_parent[u]);
        return set_parent[u];
    }
}
int main(void)
{
    char winFlag = 1;
    int i,N,M;
    char msg[5];
    int x,y;
    memset(set_parent,0xFF,sizeof(set_parent));
    memset(in_degree,0,sizeof(in_degree));
    scanf("%d%d",&N,&M);
    for(i=0;i<M;i++)
    {
        scanf("%d%s%d",&x,msg,&y);
        node[i].u = x;
        node[i].v = y;
        node[i].op = msg[0];
        if(node[i].op == '=')
        {
            set_union(node[i].u,node[i].v);
        }
    }
    for(i=0;i<M && winFlag==1;i++)
    {
        if(node[i].op == '>')
        {
            x = set_findParent(node[i].u);
            y = set_findParent(node[i].v);
            if(x==y)
            {
                winFlag = 0;
                break;
            }
            else
            {
                x=graph_vertexID(x);
                y=graph_vertexID(y);
                graph_add_edge(x,y);
            }
        }
    }
    if(winFlag)
    {
        queue<int> Q;
        int num_deleteVertex = 0;
        for(i=0;i<num_vertex;i++)
        {
            if(in_degree[i]==0)
            {
                Q.push(i);
            }
        }
        while(Q.size()>0)
        {
            x = Q.front();
            Q.pop();
            num_deleteVertex +=1;
            for(int j=0;j<G[x].size();j++)
            {
                y = G[x][j];
                in_degree[y] -=1;
                if(in_degree[y]==0)
                {
                    Q.push(y);
                }
            }
        }
        if(num_deleteVertex != num_vertex)
        {
            winFlag = 0;
        }
    }
    if(winFlag)
    {
        printf("consistent\n");
    }
    else
    {
        printf("inconsistent\n");
    }
    return 0;
}

C++
​x
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXM 250002
#define MAXN 50002
#include <vector>
using std::vector;
#include <queue>
using std::queue;
#include <map>
using std::map;
struct Node
{
    int u,v;
    char op;
} node[MAXM];
vector<int> G[MAXN];
int in_degree[MAXN];
map<int,int> vertexIdMap;
int num_vertex=0;
void graph_add_edge(int u,int v)
{
    G[v].push_back(u);
    in_degree[u]+=1;
}
int graph_vertexID(int v)
{
    if(vertexIdMap.count(v))
    {
        return vertexIdMap[v];
    }
    else
    {
        vertexIdMap[v] = num_vertex ;
        num_vertex +=1;
        return vertexIdMap[v];
    }
}
int set_parent[MAXN];
int set_findParent(int u);
void set_union(int u,int v)
{
    int x = set_findParent(u);
    int y = set_findParent(v);
    if(x!=y)
    {
        if(set_parent[x] < set_parent[y])
        {
            set_parent[x] += set_parent[y];
            set_parent[y] = x;
        }
        else
        {
            set_parent[y] += set_parent[x];
            set_parent[x] = y;
        }
    }
}
int set_findParent(int u)
{
    if(set_parent[u]<0)
        return u;
    else
    {
        set_parent[u] = set_findParent(set_parent[u]);
        return set_parent[u];
    }
}
int main(void)
{
    char winFlag = 1;
    int i,N,M;
    char msg[5];
    int x,y;
    memset(set_parent,0xFF,sizeof(set_parent));
    memset(in_degree,0,sizeof(in_degree));
    scanf("%d%d",&N,&M);
    for(i=0;i<M;i++)
    {
        scanf("%d%s%d",&x,msg,&y);
        node[i].u = x;
        node[i].v = y;
        node[i].op = msg[0];
        if(node[i].op == '=')
        {
            set_union(node[i].u,node[i].v);
        }
    }
    for(i=0;i<M && winFlag==1;i++)
    {
        if(node[i].op == '>')
        {
            x = set_findParent(node[i].u);
            y = set_findParent(node[i].v);
            if(x==y)
            {
                winFlag = 0;
                break;
            }
            else
            {
                x=graph_vertexID(x);
                y=graph_vertexID(y);
                graph_add_edge(x,y);
            }
        }
    }
    if(winFlag)
    {
        queue<int> Q;
        int num_deleteVertex = 0;
        for(i=0;i<num_vertex;i++)
        {
            if(in_degree[i]==0)
            {
                Q.push(i);
            }
        }
        while(Q.size()>0)
        {
            x = Q.front();
            Q.pop();
            num_deleteVertex +=1;
            for(int j=0;j<G[x].size();j++)
            {
                y = G[x][j];
                in_degree[y] -=1;
                if(in_degree[y]==0)
                {
                    Q.push(y);
                }
            }
        }
        if(num_deleteVertex != num_vertex)
        {
            winFlag = 0;
        }
    }
    if(winFlag)
    {
        printf("consistent\n");
    }
    else
    {
        printf("inconsistent\n");
    }
    return 0;
}

FAINT

malic自留地

[Kattis] Chess Tournament 题目分析

2020年3月8日 malic Comments 0 Comment

题面：

分析：

发表回复取消回复

题面：

分析：

发表回复 取消回复

发表回复取消回复