[综合] 紫书 习题 11-3 UVa 820 （最大流裸题）

注意这道题是双向边，然后直接套模板就ok了。 #include<cstdio> #include<algorithm> #include<vector> #include<queue> #include<cstring> #defineRE...

[综合] 紫书 习题 11-4 UVa 1660 （网络流拆点法）

这道题改了两天…… 因为这道题和节点有关，所以就用拆点法解决节点的容量问题。 节点拆成两个点，连一条弧容量为1，表示只能经过一次。 然后图中的弧容量无限。 然后求最小割，即最大流，即为答案。 固定一个源点，然后枚举汇点，然后求最小的最小割就ok了。 这里的拆点法连边的时候是拆出来的点连上原来的点。 ...

[综合] 紫书 习题11-11 UVa 1644 （并查集）

这道题感觉思路非常巧妙，我是看了别人的博客才想明白的。 这里用到了并查集，以根节点为中心城市，然后把边从大到小排序，每次的当前的边即为容量， 因为是目前的最小值，然后去算总的容量，每次选容量大的点作为新的根节点，也就是新的 中心城市。细节见代码。 #include<cstdio> #i...

[综合] 紫书 习题 11-7 UVa 10801 (单源最短路变形)

把每个电梯口看作一个节点，然后计算边的权值的时候处理一下，就ok了。 #include<cstdio> #include<vector> #include<queue> #include<cmath> #defineREP(i,a,b)for(in...

[综合] 紫书 习题 11-8 UVa 1663 （最大流求二分图最大基数匹配）

很奇怪，看到网上用的都是匈牙利算法求最大基数匹配 紫书上压根没讲这个算法，而是用最大流求的。 难道是因为第一个人用匈牙利算法然后其他所有的博客都是看这个博客的吗？ 很有可能…… 回归正题。 题目中只差一个数字的时候可以匹配，然后求最少模板数。 那么肯定匹配的越多就越少，也就是求最多...

[综合] 紫书 例题 11-12 UVa 1515 （最大流最小割）

这道题要分隔草和洞，然后刘汝佳就想到了“割”（不知道他怎么想的，反正我没想到） 然后就按照这个思路走，网络流建模然后求最大流最小割。 分成两部分，S和草连，洞和T连 外围的草和S连一条无穷大的弧，表示不能割，若原来是洞就改成草然后加上花费。 然后非外围的草和S连一条容量为把草变成洞花费的弧，...

[综合] 紫书 例题 11-14 UVa 1279 （动点最小生成树）（详细解释）

这道题写了好久…… 在三维空间里面有动的点，然后求有几次最小生成树。 其实很容易发现，在最小生成树切换的时候，在这个时候一定有两条边相等， 而且等一下更大的那条边在最小生成树中，等一下更小的边不在最小生成树中。 这样的话过了这个时刻，等一下更小的边就会代替等一下更大的边，从而最小生成树切换 ...

[综合] 欧拉回路模板

（1）判断 欧拉回路（把所有边走一遍，最后回到起点） 无向图的所有点度数为偶数，且联通 有向图的所有点入度=出度，且联通 欧拉道路（把所有边走一遍，不回到起点） 无向图所有点的度数为偶数或者除了两个度数为奇数外其余的全是偶数。同时要联通（忽略方向） 有向图所有点出度=入度或者一个顶点出度=入度+1，...

[综合] 紫书 例题 11-13 UVa 10735（混合图的欧拉回路）（最大流）

这道题写了两个多小时…… 首先讲一下怎么建模 我们的目的是让所有点的出度等于入度 那么我们可以把点分为两部分，一部分出度大于入度，一部分入度大于出度 那么显然，按照书里的思路，将边方向后，就相当于从出度大于入度的运一个流量到 入度大于出度的点。 ...

[综合] 紫书 习题 11-9 UVa 12549 （二分图最小点覆盖）

用到了二分图的一些性质，最大匹配数=最小点覆盖 貌似在白书上有讲 还不是很懂，自己看着别人的博客用网络流写了一遍 反正以后学白书应该会系统学二分图的，紫书上没讲深。 目前就这样吧。 #include<cstdio> #include<vector> #include<c...

[综合] 紫书 习题 11-12 UVa 1665 （并查集维护联通分量）

这道题要逆向思维 反过来从大到小枚举，就是在矩阵中一点一点加进去数字，这样比较 好操作，如果正着做就要一点一点删除数字，不好做。 我们需要在这个过程中维护联通块的个数，这里用到了并查集。 首先加进去一个数，联通分量数字先加一，然后再考虑有没有和其他联通分量 相连。从当前位置四个方向枚举，...

[综合] 紫书 例题 10-1 UVa 11582 （unsigned long long＋模）

（1）这道题要用到unsignedlonglong，弄了我好久 这道题范围可以达到2的64次方-1，而longlong最多到2的63次方-1， 而unsignedlonglong可以到2的64次方-1，所以要用这个类型，注意这个类型只有正数 输入输出用printf貌似要用%llu，我直接用cinco...

[综合] 紫书 例题 10-2 UVa 12169 （暴力枚举）

就是暴力枚举a，b然后和题目给的数据比较就ok了。 刘汝佳这道题的讲解有点迷，书上讲有x1和a可以算出x2，但是很明显x2=(a*x1+ｂ) 没有ｂ怎么算x2？然后我就思考了很久，最后去看他的代码发现他的代码和他讲的是两回事 他的代码里直接是枚举ａ和ｂ，不是按照书上的思路来的。 有点迷 #inclu...

[综合] 紫书 例题 10-3 UVa 10375 （唯一分解定理）

这道题感觉非常的秀 因为结果会很大，所以就质因数分解分开来算 非常的巧妙！ #include<cstdio> #include<vector> #include<cstring> #include<cmath> #defineREP(i,a,b)for...

[综合] 紫书 例题 10-４ UVa 10791（唯一分解定理）

首先分解，然后可以发现同一个因子ａｉ不能存在于两个以上的数中 因为求的是最小公倍数，如果有的话就可以约掉 所以数字必然由ａｉ的ｐｉ次方的乘积组成，那么显然，在 ａ最小为２，而ｂ大于２的情况下ａ＊ｂ＞ａ＋ｂ 所以要让和最小，就每一个ａｉ的ｐｉ次方作为一个数就好了。 另外注意longlong，素数和１ ...

[综合] 紫书 例题 10-5 UVa 12716 （枚举方式）

设gcd(a,b)=axorb=c 那么我们可以证明ｃ＝ａ－ｂ 那么同时ｃ又是ａ的因子（ｃ是ａ与ｂ的最大公因数） 所以我们可以枚举ｃ，然后枚举ｃ的倍数，也就是ａ 有了ａ和ｃ可以算出ｂ为ａ－ｃ 然后最后验算是否axorb=c就ｏｋ了。 这里的枚举方式非常的巧妙，是反过来枚举ｃ 来推ａ，如果枚举ａ的因子...

[综合] 紫书 例题 10-6 UVa 1635 （二项式定理+唯一分解定理）

首先可以发现按照题目的算法最后得出来是一个杨辉三角 如果ai的系数是m的倍数，那么i即为答案 因为这个系数可能很大，而我们只需要判断倍数 所以我们就把m分解质因数，然后判断每一个系数 的质因数的幂是不是大于等于m的该质因数的幂 然后注意第一个和最后一个可以不用判断 还有原来的杨辉三角是从0开始算的，...

[综合] 紫书 例题 10-7 UVa 10820 （欧拉函数）

这道题要找二元组（x，y）满足1<=x,y<=n且x与y互素 那么我就可以假设x<y，设这时答案为f(n) 那么答案就为2*f(n)+１（ｘ与ｙ反过来就乘２，加上（１，１）） 那么f(n)可以用欧拉函数求 显然f(n)=phi(2)+phi(3)+……+phi(n) #includ...

[综合] 紫书 例题 10-8 UVa 1262 （暴力枚举）

递归一遍遍历所有情况就ｏｋ了 #include<cstdio> #include<cstring> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constintMAXN=10; charmap[2...

[综合] 紫书 例题 10-９ UVa 1636 （概率计算）

小学数学问题 记得分数比较的时候可以交叉相乘（同号） #include<cstdio> #include<cstring> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;intmain() {cha...