html5网站优点,公司注销后网站备案吗,画廊网站模板 frontpage,网站开发公司怎么查链接#xff1a;
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 UPD:数据保证不会有两条控制链控制的据点完全相同#xff0c;也保证不会有某条控制链两端控制的据点相同…链接
时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 UPD:数据保证不会有两条控制链控制的据点完全相同也保证不会有某条控制链两端控制的据点相同。 牛妹最近沉迷于一个名为 ingress 的游戏中… 游戏中蓝绿营两个对立阵营互相角力通过争夺据点来控制区域。 具体来说二维的平面上分布有若干据点玩家可以通过XM扫描器来控制这些据点。 同一阵营控制的两个据点可以相连成为一条被该阵营控制的链。 而同一阵营控制的三条链首尾相接可以形成一块被该阵营控制的区域。 如下图为一块被蓝方控制的区域 但是这样的游戏没有一个胜利或失败结局牛牛觉得很不舒服于是他开发出了 imgress。 这个游戏和 ingress 的区别在于如果一个阵营控制了一块区域则形成这块区域的据点无法再被另一阵营控制。 此外imgress 的玩家并非直接对据点进行控制而是通过在据点间形成控制链来间接控制对应据点于是可能出现同一个据点被两方的控制链所使用的情况。 现在牛妹加入了蓝方阵营她已经得知了场上的总据点数和蓝方已经形成的所有控制链。 现在她想知道目前场上是否可能已经存在被玩家控制的区域你需要帮她解决这个问题。 输入描述: 第一行一个正整数 T表示数据组数。 每组数据的第一行有两个正整数 n 和 m表示场上总据点数为 n此时蓝方已经形成了 m 条控制链。 接下来 m 行每行有两个正整数 x 和 y表示这条控制链由据点 x 和据点 y 形成。 输出描述: 对于每组数据如果目前场上有可能存在被玩家控制的区域则输出一行 “yes”否则输出一行 “no”。均不包含引号 示例1 输入
2
3 3
1 2
2 3
3 1
5 5
1 2
2 3
3 4
4 5
5 1输出
yes
no说明 对于第一组数据蓝方在所有据点间形成了控制链此时的情况如下图所示 可以发现蓝方已经形成了控制区域。 对于第二组数据蓝方的 5 条控制链首尾相接如下图所示 此时蓝方没有形成控制区域同时可以发现绿方即使控制了所有蓝方没有控制的链也无法形成控制区域。 题意
我来把题目浓缩下就是给你一个无向图问这个图和它的补图是否存在三元环 如果图本身有三元环就是蓝方赢如补图有三元环就是绿方赢但题目是问你蓝绿方有一方能赢就输出yes都不能就输出no
题解
有一个结论如果点6的话它以及它的补图一定存在三元环。 网上说这个叫拉姆塞结论我们离散也没讲过 点数小于6的话暴力就OK了先标记给的边三层for循环看看任意三个边能不能构成环。
代码
#includebits/stdc.h
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int mod 1e9 7;
const int maxn102;
int n,sum;
int f[102][102];
void biaoji(int x,int y)
{f[x][y]1;f[y][x]1;
}
int main()
{int T,n,m,a,b;cinT;while(T--){sum0;mem(f);cinnm;for(int i1;im;i){cinab;biaoji(a,b);}if(n6){coutyes; }else{for(int i1;in;i)for(int ji1;jn;j)for(int kj1;kn;k){int wf[i][j]f[j][k]f[k][i];if(w0||w3)sum;if(sum)break;}if(sum)coutyesendl;else coutnoendl;}}
}
