ccf.zip

  • sirhhh
    了解作者
  • Dev C++
    开发工具
  • 17KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2020-02-28 18:05
    上传日期
对一些ccf题目的分析及解答,包含基本算法与逻辑。
ccf.zip
  • ccf
  • ccf,火车票问题,整组处理,减少代码数量.cpp
    3.2KB
  • ccf,炉石传说.cpp
    1.5KB
  • ccf201703-4,地铁修建,kruskal+并查集.cpp
    818B
  • ccf,老师还钥匙问题,优先队列,对于”小于号的重载“(有多种排序).cpp
    2.2KB
  • ccf,201503-4,网络延迟.cpp
    1.3KB
  • dfs,暴力搜索。图着色问题。蓝桥杯,分考场.cpp
    3.2KB
  • ccf 201812-3 CIDR合并.cpp
    2.9KB
  • ccf,命令行选择.cpp
    2KB
  • ccf2017909-4,通信网络,dfs的一种使用.cpp
    839B
  • ccf201612-3,权限查询.cpp
    3KB
  • ccf201409-4,最优配餐,bfs.cpp
    1.2KB
  • dijkstra,ccf201712-4 行车路线.cpp
    1.9KB
  • ccf201709-3,json查询.cpp
    2.5KB
  • ccf201403-4,无线网络,bfs.cpp
    1.1KB
  • dijkstra算法,ccf201609-4.cpp
    1.9KB
内容介绍
//蓝桥杯 分考场问题 //图着色问题的一种, //该题求最少着色数(不能使用贪心算法)。还有一种可能是求 给定m种颜色,共有几种上色方案。 //这两种思路均使用dfs,枚举每种可能性。 //使用set后虽然代码相对简洁,减少内存使用空间;但是会大大增加程序运行速度。 //看最下面,使用邻接矩阵来存储 #include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<climits> #include<set> using namespace std; set<int> adj[100]; //使用set存储,将有关系的放到一个集合里面 int rnum[100]={0}; //定义当前每个room中的人数 int room[100][100]={0};//room[i][j]表示第i个房间中第j个人的编号。 int reg=INT_MAX,n; void dfs(int k,int m){//第k个学生要进行分配,当前已经有m个房间了,一共有n个学生 if(m>=reg) //当前分配的房间数已经大于等于历史最少分配,则剪枝,不需要再深搜了。 return ; if(k==n+1){ //前n个学生都已经分配完了。 if(reg>m) reg=m; return; } for(int i=1;i<=m;i++){ //从第1个房间到第m个房间 bool flag=true; for(int j=0;j<rnum[i];j++){ //学生从位置0开始放 int a=room[i][j]; // 第i个房间里的j名学生 if(adj[k].count(a)){ flag=false; break; } } if(flag){ room[i][rnum[i]++]=k; dfs(k+1,m) ; //为下一个学生寻找房间 rnum[i]--;//回溯 } } //第k名学生不放在前m的房间里,重新为他分配一个房间。 room[m+1][rnum[m+1]++]=k; dfs(k+1,m+1); rnum[m+1]--; } int main(){ int m,a,b; cin>>n>>m; while(m--){ cin>>a>>b; adj[a].insert(b); adj[b].insert(a); } dfs(1,0); cout<<reg<<endl; return 0; } /* #include<iostream> #include<cstring> #include<algorithm rel='nofollow' onclick='return false;'> using namespace std; const int MAXN = (int)1e3 + 10; const int INF = (int)2e9 + 10; int G[MAXN][MAXN];//G[i][j]=1表示i和j认识,否则不认识 int stu[MAXN][MAXN];//stu[i][j]=x 表示第i个房间第j个人是编号为x的学生 int room[MAXN];//room[i]=k 表示第i个房间有k个人 int res = INF;//假设一开始需要无穷多个房间 int n,m,a,b; void dfs(int x,int total){ //x表示当前学生的编号,total表示用掉房间的数量 if (total >= res) //如果当前用掉房间的数量大于历史用掉的最小数量,返回 return; if (x == n + 1){ //如果学生已经安排完了,取最优值,并返回 res = min(total, res); return; } for (int i = 1; i <= total; i++){ //遍历所有房间 int k = 0; //计数器 int len = room[i]; //第i个房间的有多少人 for (int j = 1; j <= len; j++){ //遍历当前房间的所有学生 if (!G[x][stu[i][j]]) //如果学生x与学生stu[i][j]没有关联,k++; k++; } if (k == len){ //如果x与当前房间所有的人都没有关联 stu[i][++room[i]] = x; //那么就把x放进这个房间里 dfs(x + 1, total); //当前学生已经被安排,dfs安排下一个学生 room[i]--; //回溯 } } //如果所有房间都与x有关,则要另开一间新的房间安排给x stu[total+1][++room[total+1]] = x; dfs(x + 1, total+1); //安排下一个学生 room[total+1]--;//回溯 } int main() { ios::sync_with_stdio(false); //加快cin的输入 cin >> n>>m; memset(G,0,sizeof(G)); memset(stu, 0, sizeof(stu)); memset(room, 0, sizeof(room)); for (int i = 1; i <= m; i++){ cin >> a >> b; G[a][b] = G[b][a] = 1; } dfs(1, 0); cout << res << endl; return 0; } */
评论
    相关推荐
    • 空间桁架c++.rar
      空间桁架c++结构力学计算程序,可计算空间桁架变形及应力
    • CRC-32 源代码 CC++ 都能正常编译
      本人根据 rfc1952 文档中的说明,结合zlib中的代码,简化后写出的CRC32计算代码,适用于所有能够使用CC++的平台,满足 ISO3309 要求。获得的CRC32 与在Winrar, gz, zlib中使用的完全一样。代码中有详细的使用...
    • 监视文件和记录,或在它们发生更改时触发操作。-C/C++开发
      监视人一种文件监视服务。 用途监视员的存在是为了监视文件并记录文件实际更改的时间。 匹配文件更改时,它还可以触发操作(例如重建资产)。 Documentati Watchman文件监视服务。 用途监视员的存在是为了监视文件并...
    • Apache Doris(正在孵化)-C/C++开发
      Apache Doris(正在孵化)Doris是用于报告和分析的基于MPP的交互式SQL数据仓库。 它的原始名称是在百度开发的Palo。 将其捐赠给Apache Software Foundation之后,它被重命名为Doris。 Apache Doris(正在孵化)Doris...
    • COCOS2D-X 捕鱼达人 (VS2010 C++)
      cocos2d-x2.25引擎建立的捕鱼达人,参照了《Cocos2d-x高级开发教程:制作自己的〈捕鱼达人〉》一书并做了改动。将代码导入cocos2d的projects文件夹内自创的工程文件夹里的proj.win32文件夹,resoutses则放在对应工程...
    • C++生成压缩文件源代码
      C++生成压缩文件的源代码。 可以直接引用到项目中使用。
    • ICM20648驱动 C++.zip
      icm-20648底层驱动,包含所有寄存器声明,简单的参数配置,读取加速度、陀螺仪、内部温度等函数。
    • ECC 加密算法实现 C++
      ECC 椭圆加密算法的实现C++ 直接在vs上运行
    • CCF总结.rar
      CCF考试总结,本文总结了进十几年的题型,值得参考
    • qpopper2.53.tar.Z
      pop3 server