比赛安排（穷举法或dfs）

- 日理万妓 2021-09-30 01:58 384阅读 0赞

# #

## 比赛安排 ##

时间限制: 1 Sec  内存限制: 125 MB  
提交: 11  解决: 10  
\[ [提交][Link 1]\]\[ [状态][Link 2]\]\[ [讨论版][Link 3]\]\[命题人:外部导入\]

## 题目描述 ##

设有2n（n<=6）个球队进行单循环比赛，计划在2 n – 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2n – 1天内每个队都与不同的对手比赛。

例如n=2时的比赛安排：

队           1  2                  3  4

比赛       1==2               3==4                一天

1==3               2==4                二天

1==4               2==3                三天

## 输入 ##

每个测试文件只包含一组测试数据，每组输入数据为一个正整数n（n<=6）。

## 输出 ##

对于每组输入数据，输出比赛安排，从第一天的安排开始，每天占一行，每行开头先输出天号，再输出当天的安排，优先给队伍编号小的队伍安排比赛，具体格式见样例输出。

## 样例输入 ##

## 样例输出 ##

<1>1-2,3-4
    <2>1-3,2-4
    <3>1-4,2-3

## 提示 ##

题解：因为n最大为6，那么意味着最多有64只队伍，数据不大。

想到可以穷举。看题面，要从小到大输出。

可以先试试在纸上来写，拿n=3为例，即有8只队伍比赛7天

先看第一天1可以和2，3可以和4，5可以和6，7可以和8

第二天1已经和2比赛过了，所以安排1和3，再接着看2，往后遍历，因为3已经安排和1比赛了，所以2只能和4，5的情况和仿照1的情况所以5-7,6-8。

因此穷举的过程可以得到了，第一重循环跑2^n-1天，第二重循环从小到大跑队伍，第三重循环跑当前队伍的对手，全局上需要开一个二维数组记录哪两个队伍已经比赛过了，在每一天里面，需要开一个一维数组记录在这一天，该队伍是不是已经被安排了。

代码如下：

#include<bits/stdc++.h>
    
    using namespace std;
    
    int main()
    
    {
    
        int n;   
    
        while(cin>>n)
    
        {
    
            int da=pow(2.0,n)-1; //代表比赛的天数
    
            int me=da+1;     //代表比赛的队伍数量
    
            bool dp[70][70];  //记录哪两只队伍已经比赛过
    
            bool vis[70];    //记录一天里该队伍是否已经有比赛安排了
    
            memset(dp,0,sizeof(dp)); //初始化为0
    
            for(int i=1;i<=da;i++)  //循环da天
    
            {
    
                int q=0;     //控制输出格式的变量
    
                memset(vis,0,sizeof(vis));//每一天的vis数组均需要初始化
    
                cout<<"<"<<i<<">"; //输出每一天的格式要求
    
                for(int j=1;j<=me;j++)  //从小到大循环遍历每一只队伍
    
                {
    
                   if(vis[j]==1)continue;  //如果第j只队伍已经作为了前面队伍的对手则跳过
    
                   vis[j]=1; //开始安排第j只队伍的对手，并标记已经便利过
    
                   for(int k=j+1;k<=me;k++) //因为按规律得在“-”左边的队伍一定是小于右边的队伍（即对手）
    
                   {
    
                       if(vis[k]==0&&dp[j][k]==0) //如果从小到大找到队伍k，且j队伍与k队伍没有比赛过而且k队伍在1当天还没有安排则安排j与k比赛
    
                       {
    
                           dp[j][k]=1;   //记录j和k已经比赛过
    
                           vis[k]=1;     //标记k队伍在这一天里已经有比赛安排
    
                           if(q++)cout<<","; //控制输出个数
    
                           cout<<j<<"-"<<k;
    
                           break; //找到一场比赛后 跳出找接下来的比赛。
    
                       }
    
                   }
    
                }
    
                cout<<endl;
    
            }
    
        }
    
        return 0;
    
    }

我的dfs代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    int n;
    int v[105];
    int vs[105][105];
    int s;
    queue<int>q;
    int p=1;
     
    void display()
    {
        cout<<"<"<<p<<">";p++;
        while(!q.empty ())
        {
            int x=q.front ();q.pop();
            int y=q.front ();q.pop();
            cout<<x<<"-"<<y;
            if(q.empty ()) cout<<endl;
            else cout<<",";
        }
    }
     
     
    void dfs(int k,int m)
    {
        for(int j=k+1;j<=(1<<n);j++)
        {
            if(!v[j]&&!vs[k][j])
            {
                q.push(k);
                q.push(j);
                vs[k][j]=1;
                v[k]=1;
                v[j]=1;
                m+=2;
                if(m==s)
                {
                    memset(v,0,sizeof(v));
                    v[1]=1;
                    display();
                    return;
                }
                for(int i=1;i<=(1<<n);i++)
                {
                    if(!v[i]) 
                    {
                        dfs(i,m);
                        return;
                    }
                }
            }
        }
    }
     
     
     
     
     
    int main()
    {
        cin>>n;
        s=(1<<n);
        while(!q.empty()) q.pop();
        memset(v,0,sizeof(v));
        memset(vs,0,sizeof(vs));
        if(n==1) cout<<"<"<<1<<">"<<1<<"-"<<2;
        else
        {
            v[1]=1;
        for(int i=2;i<=(1<<n);i++)
        {
            if(v[i]==0)
            {
                q.push(1);
                q.push(i);
                v[i]=1;
                for(int j=1;j<=(1<<n);j++)
                {
                    if(!v[j])
                    {
                        dfs(j,2);
                        break;
                    }
                }
            }
        }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/caiyishuai/p/8576809.html

[Link 1]: http://acm.ocrosoft.com/submitpage.php?cid=1034&pid=8&langmask=0
[Link 2]: http://acm.ocrosoft.com/problemstatus.php?id=3019
[Link 3]: http://acm.ocrosoft.com/bbs.php?pid=3019&cid=1034
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/9250a539f03849aca94f8687cc97d723.png