门户网站的首页模板,苏州建网站收费,起零网站建设,网站建设需要审批吗题目链接 引用自晴神OJA - 边覆盖B - 极大独立集C - 稳定婚姻问题D - 笛卡尔树没赶得上全程的比赛#xff0c;就做了两道#xff0c;后面两道以后有时间再补。两道都是概念题#xff0c;比较基础~ 以下是题解A - 边覆盖Case Time Limit: 200 MS (Others) / 400 MS (Java) …题目链接 引用自晴神OJA - 边覆盖B - 极大独立集C - 稳定婚姻问题D - 笛卡尔树没赶得上全程的比赛就做了两道后面两道以后有时间再补。两道都是概念题比较基础~ 以下是题解A - 边覆盖Case Time Limit: 200 MS (Others) / 400 MS (Java) Case Memory Limit: 256 MB (Others) / 512 MB (Java)Accepted:199 Total Submission:362Problem Description对一个给定的无向图G(V,E)边集E是E的子集。如果V中的所有顶点都在E中出现过那么称边集E是图G的一个边覆盖(Edge Cover)。(以上定义引自https://en.wikipedia.org/wiki/Edge_cover)根据上面的定义请判断一些给定的边集是否是给定的无向图的边覆盖。Input每个输入文件一组数据。第一行为两个整数N、M(1N500, 1MN*(N-1)/2)分别表示无向图的顶点数和边数。假设图上的顶点编号为从1到N。接下来M行每行两个正整数u、v(1u,vN, u!v)分别表示一条无向边的两个端点。数据保证没有重边。接着一个正整数K(K10)表示查询的个数。然后是K个查询每个查询第一行为一个正整数L(LM)表示欲查询边集E中的边数接下来L行每行两个整数表示边集E中的一条边。数据保证E一定是E的子集。Output每个查询一行如果欲查询边集E不是图G的边覆盖那么输出No否则输出Yes。Sample Input6 71 21 32 32 43 54 54 6331 23 54 641 22 34 54 631 22 34 612345678910111213141516171819202122Sample OutputYesYesNoAuthorShoutmonSource19浙大考研机试模拟赛分析题目是中文题意思是输入一堆边看这些边是否将所有顶点都覆盖到了。只需要在每次查询输入后将边所连的顶点置为已访问再遍历一次访问数组即可。#include #include#include#include#include#include#includeusing namespacestd;const int maxn510;intG[maxn][maxn];boolvis[maxn];intmain(){//freopen(1.txt,r,stdin);intn,m;cinnm;intu,v;for(int i0;iscanf(%d%d,u,v);G[u][v]1;G[v][u]1;}intk;cink;while(k--){intL;scanf(%d,L);memset(vis,0,sizeof(vis));for(int i0;iscanf(%d%d,u,v);vis[u]true;vis[v]true;}intj;for(j1;jn;j){if(vis[j]false){printf(No\n);break;}}if(jn1) printf(Yes\n);}return 0;}View CodeB - 极大独立集Case Time Limit: 100 MS (Others) / 200 MS (Java) Case Memory Limit: 256 MB (Others) / 512 MB (Java)Accepted:140 Total Submission:303Problem Description对一个给定的无向图G(V,E)点集V是V的子集。如果V中的任意两个顶点之间都没有边就称点集V是图G的独立集(Independent Set)。在此基础上如果往V中添加任何一个在V中但不在V中的顶点都会使V变成非独立集那么就称V是图G的极大独立集(Maximal Independent Set)。(以上定义引自https://en.wikipedia.org/wiki/Independent_set_(graph_theory))根据上面的定义请判断一些给定的点集是否是给定的无向图的极大独立集。Input每个输入文件一组数据。第一行为两个整数N、M(1N500, 1MN*(N-1)/2)分别表示无向图的顶点数和边数。假设图上的顶点编号为从1到N。接下来M行每行两个正整数u、v(1u,vN, u!v)分别表示一条无向边的两个端点。数据保证没有重边。接着一个正整数K(K10)表示查询的个数。然后是K个查询每个查询第一行为一个正整数L(LN)表示欲查询点集V的顶点个数第二行为用空格隔开的L个正整数表示V中的顶点编号。数据保证V一定是V的子集。Output每个查询一行如果欲查询的点集不是图G的独立集那么输出Not an Independent Set如果欲查询的点集是图G的独立集但不是极大独立集那么输出Not Maximal如果欲查询的点集是图G的极大独立集输出Yes。Sample Input6 51 22 32 44 54 6321 431 3 431 2 4Sample OutputNot MaximalYesNot an Independent SetAuthorShoutmonSource19浙大考研机试模拟赛分析判断是否是极大独立集根据定义一个独立集是指任意两个顶点之间都没有边的点集所谓最大就是加入任意一个顶点都会“破坏”独立集。先判断是否是独立集然后再枚举每一个未在点集中的点判断是否在加入后会“破坏”独立集。注意到样例中已经给出了坑点即1和4仅是独立集不是最大独立集因为加入3后仍然是一个独立集知道这点以后就可以轻松解决了。#include #include#include#include#include#include#includeusing namespacestd;const int maxn510;int G[maxn][maxn]{0};boolvis[maxn];intmain(){//freopen(1.txt,r,stdin);intn,m;cinnm;intu,v;for(int i0;iscanf(%d%d,u,v);G[u][v]G[v][u]1;}intK;scanf(%d,K);loop:while(K--){intL;scanf(%d,L);vectorvec;inttemp;memset(vis,0,sizeof(vis));for(int i0;iscanf(%d,temp);vec.push_back(temp);vis[temp]true;}for(int i0;icout}}}bool flagfalse;for(int i1;in;i){if(vis[i]false){intj;for(j0;j}}if(jvec.size()){coutflagtrue;gotoloop;}}}if(!flag) cout}return 0;}View Code
