ACM题集以及各种总结大全！ 虽然退役了，但是整理一下，供小弟小妹们以后切题方便一些，但由于近来考试太多，顾退役总结延迟一段时间再写！先写一下各种分类和题集，欢迎各位大牛路过指正。 一.ACM入门 关于ACM 百度百科连接 杭州电子科技大学(hdu)ACM题目 连接 ...
深度优先搜索（DFS） 往往利用递归函数实现（隐式地使用栈）。 深度优先从最开始的状态出发，遍历所有可以到达的状态。由此可以对所有的状态进行操作，或列举出所有的状态。 1.poj2386 Lake Couting 题意：八连通被认为连接在一起，求总共有多少个水洼？ Sample Input： 10 12 W........WW. .WWW.....WWW...
目录： 1.1093D. Beautiful Graph(DFS染色) 2.514C - Watto and Mechanism(Tire) 3.69E.Subsegments(STL) 4.25C. Roads in Berland(最短路松弛操作) 5.128B. String Problem (floyd预处理) 6.33C.Wonderful Ra...
书上的欧拉回路定义不在重复，欧拉回路定义， 弗洛莱走边的方法也不再细讲，弗洛莱算法描述 这里只说怎么进行代码实现。 /* 无向图的欧拉回路 邻接矩阵存图 原理： dfs走边，当走不动时就将其放入栈中,最后将顶点从栈中取出的顺序就是欧拉路径。 如果走错边则必定会堵，那么就会将堵的放入栈中，从栈中取出的话就看作是最后走的割边，符合弗洛来算法； 如果走的...
Problem Description 有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？ Input n： 表示有n对夫妻被邀请 (n<= 1000)m： 表示有m 对矛盾关系 ( m...
#include<bits/stdc++.h> using namespace std; const int N=510; const int inf=0x3f3f3f3f; int mp[N][N]; bool vis[N]; int dis[N]; int n,m,s,D; int cost[N][N]; vector<int&g...
剪枝，顾名思义，就是通过一些判断，砍掉搜索树上不必要的子树。有时候，我们会发现某个结点对应的子树的状态都不是我们要的结果，那么我们其实没必要对这个分支进行搜索，砍掉这个子树，就是剪枝。 可行性剪枝 给定n个整数，要求选出K个数，使得选出来的K个数的和为sum。 在搜索时，如果已经选了k个数，再往后选多的数是没有意义的。所以我们可以直接减去这个搜索分支。 又...
概述 在一个无向图中，若删除某个点u后连通分量数目增加，则称点u为该无向图的一个割点(cut vertex) 引理 无向连通图DFS树 从一个节点出发进行DFS，将后访问的结点设为前访问结点的孩子，DFS经过的边叫做DFS树的树边(tree edge)，第一次处理时从后代(descendant)指向祖先(ancestor)的边叫做返祖边(back edge...
在上一篇博客判断有向图是否有圈中从递归的角度简单感性的介绍了如何修改深度优先搜索来判断一个有向图是否有圈。事实上， 它的实质是利用了深度优先生成树（depth-first spanning tree）的性质。那么什么是深度优先生成树？顾名思义，这颗树由深度优先搜索而生成的，由于无向图与有向图的深度优先生成树有差别，下面将分别介绍。 一. 无向图的深度优先生...
Wormholes Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 <= N <= 12, N even) to materialize on his farm,...