首页 > 代码库 > hdu 6029 Graph Theory
hdu 6029 Graph Theory
题目链接：hdu 6029 Graph Theory
题意：
有n个点，每个点按标号排序，现在每个点有两种操作，1表示将这个点和之前全部的点连一条边，2表示没有操作。
现在问你是否有一个边集能构成完美匹配。
完美匹配的定义为：1.每个点有且只有一条边。2.每条边的两端都没有重叠的点。
题解：
首先n为奇数的时候肯定是不行的，然后对于n为偶数的时候for一遍，看看有哪些点没有被匹配到。
1 #include<cstdio> 2 int t,n,x,cnt; 3 int main(){ 4 scanf("%d",&t); 5 while(t--){ 6 scanf("%d",&n),cnt=1; 7 for(int i=1;i<n;i++){ 8 scanf("%d",&x); 9 if(x==1&&cnt)cnt--; 10 else if(x==2)cnt++; 11 } 12 puts((cnt||n&1)?"No":"Yes"); 13 } 14 return 0; 15 }
hdu 6029 Graph Theory
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。