shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共6篇）

边的染色来自专栏

前言: 思维不够,看到这种陌生的题目无从下手. 思路: 这题应该做过一次的人会觉得它其实并不难.主要思想:把边权->点权.这样做的好处是,无论你怎么分配点权,在环内的异或值一定为(前提是环内的一定合法.)做题步骤也是围绕这些性质来的.1.首先判断给定的点是否有矛盾,就是你给一个点赋值,它假如是...

dfs 图论

2021-01-28

2 688

图的遍历来自专栏

前言: 这是一个很不错的思维题! 思路: 这个题就是要让我们来证明一幅图必须有奇数环,才能使得全图被遍历(假如按2步走的话).首先我们对于一棵树来说,我们知道假如我们不走到叶子节点再还回肯定是没有意义的,但是其实我们走到叶子节点再还回也是没有意义的.比方说我们现在有两条链,奇数链和偶数链.奇数链:1...

图论

2021-01-13

3 685

Exercise Route 来自专栏

很难的一个题目(对我这种图论蒟蒻来说).首先你得会的算法有:lca,dfs(居然没了...这个题的解法分为三步:1.转化题意:原本的题意是给你n个点,m条边,前n-1条是树边,后面的边和树边可以形成多少个环?->成环可以转化为,a->b的路径和c->d的路径有交集.我们去掉交集就是...

LCA DFS 图论

2020-09-11

1 626

Cycles 来自专栏

先构造完全图,然后根据完全图构造非完全图即可. #include <bits/stdc++.h> using namespace std; const int N=105; int c_3[N],c_2[N*5]; int ans[N][N]; int main() { int ...

构造图论

2020-09-10

1 614

Bear and Two Paths 来自专栏

一个简单的构造题,首先4个点是构造不出来的,5个点必需是a,c连边,b,d连边,中间一条链即可,最少需要n+1条边...这题就结束了2333 #include <bits/stdc++.h> using namespace std; int main() { int n,m; ...

构造图论

2020-09-10

1 646

Jamie and Interesting Graph 来自专栏

看上去很复杂,其实你只要把构造一条链,使得他们的和为1e6+3(>n的质数),就好了,然后其他边为1e9,然后就ac了.代码如下: #include <bits/stdc++.h> using namespace std; const int N=2e5+5; struct vv{...

图论

2020-09-08

1 528