CodeForces King of the Waves(DFS )

71 阅读 0 评论 47 点赞

我是靠谱客的博主落后爆米花，最近开发中收集的这篇文章主要介绍CodeForces King of the Waves(DFS )，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：已知– ’1’ if person i will win against person j.（1代表i能赢j）
– ’0’ if person i will lose against person j.（0代表i会输给j）

– ’X’ if i = j.（X代表平局）。

有n个人（0~n-1），问怎么安排出场顺序能使0赢。

思路：一开始觉得排在前面的一定能被后边的打败，从而忽略了0可以打败多个的事实。用DFS搜索只有部分数据通过。
其实可以将问题简化为如果0能胜利，则剩余的n-1个人要么被0打败，要么被0所打败的人打败这几种情况，也就说在DFS的时候从0开始搜索，能被0打败的放入串中，如果串在等于n之前断了，继续从0的下一条串遍历（0能打败的人不止一个的情况下），只要这n-1个人都能被0或其他0所打败的人打败，被遍历到vis[i]都为1即可（即在DFS回溯的时候之前有对手被打败的就不在恢复为遍历之前的状态）。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int Map[1005][1005];///存图
int vis[1005];///标记是否被遍历
int ans[1005];///存出场顺序
int n,cnt,flag;
void DFS(int a)
{
    if(cnt==n)
    {
        flag=1;
        return;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(Map[a][i]==1&&vis[i]==0)
            {
                vis[i]=1;///i能被a打败，则加入串中
                ans[cnt++]=i;///计数增加
                DFS(i);
            }
        }
    }
}
int main()
{
    flag=0;
    scanf("%d%*c",&n);
    char e;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%c",&e);
            if(e=='X')
                Map[i][j]=2;
            else
                Map[i][j]=e-'0';
        }
        getchar();
    }
    /*for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            cout<<Map[i][j]<<" ";
        cout<<endl;
    }*/
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    cnt=1;
    DFS(0);
    if(flag==0) printf("impossiblen");
    else
    {
        for(int i=cnt-1;i>=0;i--)
            printf("%d ",ans[i]);
        printf("n");
    }
    return 0;
}