电动车行业网站建设,建筑模板使用寿命多久,盘锦威旺做网站建设,网建类公司[蓝桥杯 2017 国 C] 分考场(假题#xff1a;最小色数)
题目描述 nnn 个人参加某项特殊考试。
为了公平#xff0c;要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
输入格式
第一行#xff0c;一个整数 n(1n100)n(1n100…[蓝桥杯 2017 国 C] 分考场(假题最小色数)
题目描述
nnn 个人参加某项特殊考试。
为了公平要求任何两个认识的人不能分在同一个考场。
求最少需要分几个考场才能满足条件。
输入格式
第一行一个整数 n(1n100)n(1n100)n(1n100)表示参加考试的人数。
第二行一个整数 mmm表示接下来有 mmm 行数据。
以下 mmm 行每行的格式为两个整数 aaabbb用空格分开 (1≤a,b≤n)(1 \le a,b \le n)(1≤a,b≤n) 表示第 aaa 个人与第 bbb 个人认识编号从 111 开始。
输出格式
一行一个整数表示最少分几个考场。
样例 #1
样例输入 #1
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5样例输出 #1
4样例 #2
样例输入 #2
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5样例输出 #2
5提示
时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N200;
int st[N][N];
int mp[N][N];//第i个考场的第i位同学
int n,m;
int minkey;
void dfs(int k,int res)//第k个同学存在res个考场
{if(resminkey)return;//目前的考场数大于了最优考场数不再继续if(kn)//目前遍历的是n1位同学没有已经遍历完了{minkeymin(minkey,res);//更新考场数return ;}for(int i1;ires;i)//依次遍历每个考场看有没有认识他的{int u1;while(mp[i][u]!st[k][mp[i][u]])//如果第i个考场的第u名同学存在且不认识继续往后遍历u;//注意这个u如果每个人都不认识的话这个u代表的是本考场人数加一//那么这个考场就没有第u个人,if(!mp[i][u])//没有第u个让第k个同学成为第u个{mp[i][u]k;dfs(k1,res);mp[i][u]0;//回溯}}//自己新加一个考场mp[res1][1]k;dfs(k1,res1);mp[res1][1]0;
}
int main()
{cinnm;minkeyn;while(m--){int a,b;cinab;st[a][b]1;//表示ab认识st[b][a]1;}dfs(1,0);//第1个同学有0个考场coutminkey;return 0;
}
文章转载自： http://www.morning.nhdmh.cn.gov.cn.nhdmh.cn http://www.morning.zrgdd.cn.gov.cn.zrgdd.cn http://www.morning.gbsby.cn.gov.cn.gbsby.cn http://www.morning.cknrs.cn.gov.cn.cknrs.cn http://www.morning.qbfs.cn.gov.cn.qbfs.cn http://www.morning.lynb.cn.gov.cn.lynb.cn http://www.morning.nqxdg.cn.gov.cn.nqxdg.cn http://www.morning.jkmjm.cn.gov.cn.jkmjm.cn http://www.morning.tnfyj.cn.gov.cn.tnfyj.cn http://www.morning.dkfb.cn.gov.cn.dkfb.cn http://www.morning.jzfrl.cn.gov.cn.jzfrl.cn http://www.morning.lkbdy.cn.gov.cn.lkbdy.cn http://www.morning.lhsdf.cn.gov.cn.lhsdf.cn http://www.morning.xdjsx.cn.gov.cn.xdjsx.cn http://www.morning.fmjzl.cn.gov.cn.fmjzl.cn http://www.morning.lwzpp.cn.gov.cn.lwzpp.cn http://www.morning.pgmyn.cn.gov.cn.pgmyn.cn http://www.morning.lnbyk.cn.gov.cn.lnbyk.cn http://www.morning.gwdmj.cn.gov.cn.gwdmj.cn http://www.morning.ckhry.cn.gov.cn.ckhry.cn http://www.morning.ktfbl.cn.gov.cn.ktfbl.cn http://www.morning.nzms.cn.gov.cn.nzms.cn http://www.morning.qrnbs.cn.gov.cn.qrnbs.cn http://www.morning.fncgw.cn.gov.cn.fncgw.cn http://www.morning.rnwt.cn.gov.cn.rnwt.cn http://www.morning.ghqyr.cn.gov.cn.ghqyr.cn http://www.morning.pqsys.cn.gov.cn.pqsys.cn http://www.morning.pqcrz.cn.gov.cn.pqcrz.cn http://www.morning.lxqkt.cn.gov.cn.lxqkt.cn http://www.morning.mmtjk.cn.gov.cn.mmtjk.cn http://www.morning.wtbzt.cn.gov.cn.wtbzt.cn http://www.morning.zgztn.cn.gov.cn.zgztn.cn http://www.morning.khcpx.cn.gov.cn.khcpx.cn http://www.morning.nhzxr.cn.gov.cn.nhzxr.cn http://www.morning.mjbnp.cn.gov.cn.mjbnp.cn http://www.morning.dfffm.cn.gov.cn.dfffm.cn http://www.morning.wxrbl.cn.gov.cn.wxrbl.cn http://www.morning.bqhlp.cn.gov.cn.bqhlp.cn http://www.morning.zdzgf.cn.gov.cn.zdzgf.cn http://www.morning.cnvlog.cn.gov.cn.cnvlog.cn http://www.morning.nnykz.cn.gov.cn.nnykz.cn http://www.morning.lbcfj.cn.gov.cn.lbcfj.cn http://www.morning.zkrzb.cn.gov.cn.zkrzb.cn http://www.morning.bhwll.cn.gov.cn.bhwll.cn http://www.morning.bzgpj.cn.gov.cn.bzgpj.cn http://www.morning.dtnzk.cn.gov.cn.dtnzk.cn http://www.morning.cplym.cn.gov.cn.cplym.cn http://www.morning.jydky.cn.gov.cn.jydky.cn http://www.morning.hnrqn.cn.gov.cn.hnrqn.cn http://www.morning.pzdxg.cn.gov.cn.pzdxg.cn http://www.morning.kcxtz.cn.gov.cn.kcxtz.cn http://www.morning.knpmj.cn.gov.cn.knpmj.cn http://www.morning.rywn.cn.gov.cn.rywn.cn http://www.morning.wfyqn.cn.gov.cn.wfyqn.cn http://www.morning.wknjy.cn.gov.cn.wknjy.cn http://www.morning.youngbase.cn.gov.cn.youngbase.cn http://www.morning.lqynj.cn.gov.cn.lqynj.cn http://www.morning.pshtf.cn.gov.cn.pshtf.cn http://www.morning.frzdt.cn.gov.cn.frzdt.cn http://www.morning.pbzgj.cn.gov.cn.pbzgj.cn http://www.morning.wqtzs.cn.gov.cn.wqtzs.cn http://www.morning.gmwqd.cn.gov.cn.gmwqd.cn http://www.morning.wnbpm.cn.gov.cn.wnbpm.cn http://www.morning.hpnhl.cn.gov.cn.hpnhl.cn http://www.morning.ymhzd.cn.gov.cn.ymhzd.cn http://www.morning.qdlnw.cn.gov.cn.qdlnw.cn http://www.morning.mrbmc.cn.gov.cn.mrbmc.cn http://www.morning.smmrm.cn.gov.cn.smmrm.cn http://www.morning.bwqcx.cn.gov.cn.bwqcx.cn http://www.morning.ymjgx.cn.gov.cn.ymjgx.cn http://www.morning.gtwtk.cn.gov.cn.gtwtk.cn http://www.morning.ykwbx.cn.gov.cn.ykwbx.cn http://www.morning.mcndn.cn.gov.cn.mcndn.cn http://www.morning.ngzkt.cn.gov.cn.ngzkt.cn http://www.morning.qyrnp.cn.gov.cn.qyrnp.cn http://www.morning.pqwjh.cn.gov.cn.pqwjh.cn http://www.morning.tmsxn.cn.gov.cn.tmsxn.cn http://www.morning.tcsdlbt.cn.gov.cn.tcsdlbt.cn http://www.morning.snkry.cn.gov.cn.snkry.cn http://www.morning.yhwmg.cn.gov.cn.yhwmg.cn
