LCA+tarjan+桥+dsu 蒟蒻刷到个难题。。。。。。 题目给的图一定是联通的。我们大致的想法是：先进行缩点。把图变成一个树。节点与节点之间用桥连接。这并不难，我们tarjan一下，找到桥然后染色就可以了。然后添加边时。在书上的两个节点之间连一条边。一定会构成一个环。这个环中原本的边会失去桥的属性。那么：假设在u和v之间建边。u,v的最近公共祖先为LCA。那么u->LCA v->LCA 之间的边都不在是桥。 我刚开始的代码是从u和v暴力向上找公共祖先。并一路削除路过的边的桥的属性。如果，已经是消除过的状态无妨。如果是第一次消除，那么桥的数量就减一。 #include<i...

最小费用流的水题 我们可以以每一个格点为节点建图，也可以根据曼哈顿距离建图。都无所谓。这题如果根据曼哈顿距离的话，其实还可以用KM算法去做。 这里给出费用流的dijstra写法： #include<iostream> #include<algorithm> #include<queue> using namespace std; typedef pair<int, int> pii; const int inf = 1e9; const int max_n = 1e4 + 100; const int max_m = 4 * max_n; str...

判断负圈的版子题 之前的题用Bellman法判断过了。这里就用spfa判断一下负圈吧。 用spfa判断负圈的方法有两种：1.记录节点入队的次数，若次数>n-1则有负圈2.记录起点到节点经历的边数，若边数>n-1则有负圈（也可以理解为途经的节点数） 第二种会更快一点 代码如下： #include<iostream> #include<algorithm> #include<queue> #include<cstdio> using namespace std; const int max_n = 700; const int max_m...

我们枚举后缀，以当前后缀开头为起点计算不同的子串。那么重要的就是，我要知道有多少当前后缀的前缀是重复的。即别的后缀也有。我们按照排名，遍历后缀。假如我们遍历到后缀i。然后我们知道后缀1到后缀i-1与其最长的公共前缀长为k那么后缀i能贡献出len(后缀i)-k个不同的子串而与前i-1个后缀的最长公共前缀其实就是与后缀i-1的最长公共前缀。也就是height[i]那么每一个后缀的贡献就是n-SA[i]-height[i]遍历一遍就好了 代码如下: #include<iostream> #include<algorithm> #include<cstdio> #i...

增广路 这道题，关键就是让我们判断。二分图匹配时，有哪些边是必须被用上的。一个简单朴素的思想就是：我们枚举边，删除这条边后在求其最大匹配数。看是否减少了。能过，但是复杂度其实是极高的。那我们想一想是否可以优化这个算法？事实上就是增广路的思想。我们删除这条边后，不需要再从头开始求最大匹配数。而是，我们可以在就已经匹配的基础上，再去尝试寻找一条增广路。看能不能找到。能找到就说明，这条边不是必须的。不能找到就说明这条边是必须的。复杂度一下子就降下来了。 代码如下 #include<iostream> #include<algorithm> #include<cstdio...

判断桥 代码如下： #include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef pair<int, int> pii; const int max_n = 1100; const int max_m = 1e6 + 100; struct edge{ int to, rev,next; }E[max_m << 1]; int head[max_n]; int cnt = 1; vo...

水题 注意建图，转换器是无限的。另外不能建设备。会t##代码如下 #include<iostream> #include<algorithm> #include<queue> #include<cstdio> #include<set> #include<map> using namespace std; const int max_n = 500; const int max_m = 1000; const int inf = 2e9; struct edge { int to, cap, rev, next; }E[m...

水题 反向建边，再跑一遍dij就可以了##代码如下： #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<functional> #include<cstdio> using namespace std; typedef pair<int, int> pii; const int max_n = 1200; const int inf = 2e9; const int max_m = 1e5 + 100...

二分+height分组 height分组真的很常用。我们只要二分长度就可以了。值得注意的是，第一次满足长度的height[i]此是贡献的相等的为2个后缀 代码如下 #include<iostream> #include<algorithm> #include<map> #include<cstdio> using namespace std; const int max_n = 2e4 + 100; int a[max_n]; int ranks[max_n], SA[max_n], height[max_n]; int wa[max_n], w...

二分图的判断+二分图最大匹配数 使用黑白染色法进行判断，用HK算法高效计算最大匹配数##代码如下： #include<iostream> #include<algorithm> #include<cstdio> #include<queue> using namespace std; const int inf = 2e9; const int max_n = 220; const int max_m = 41000; struct edge{ int to, next; }E[max_m << 1]; int head[max_n]...

松弛操作 我们改变松弛操作为d[v]=min(d[u],e.cost)并维护一个大顶堆。注意输出格式 代码如下： #include<iostream> #include<algorithm> #include<queue> #include<cstdio> using namespace std; typedef pair<int, int> pii; const int inf = 2e9; const int max_n = 1100; const int max_m = 1e6 + 100; struct edge{ int t...

版子题，求割点 代码如下： #include<iostream> #include<algorithm> #include<cstdio> #include<functional> using namespace std; const int max_n = 110; const int max_m = 11000; struct edge{ int to, next; }E[max_m << 1]; int head[max_n]; ;int cnt = 1; void add(int from, int to) { E[cnt]....

建图 我们可以看看如何建图。首先保证每一份食物和饮品都只使用过一次。饿哦们可以把食物建在牛的 左边，饮品建在牛的右边。食物连源点，饮品连汇点。这样就满足了。 但是还有一个要注意的地方。就是每一头牛只能用一次。也就是说，我们每一头牛只能用一次。所以，要对牛进行拆点。 代码如下： #include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<functional> using namespace std; const int inf = 2...

缩点 首先第一个任务，我们要找到至少应该发布任务的点数。我们很清楚的一点：如果这个图是一个DAG的话，我们只要在入度数为0的点处放置就可以了。但是在所给的测试样例中，我们可以看到节点1在一个环中。我们会注意到，在这个环中无论在那个点放置都可以到达所有的点。那边给了我们思路，我们先缩点，将图变为一个DAG。然后第一个答案就是此是入度为0的缩点数。 那第二个答案呢？我们要选择连最少的边使得整个图都是一个强连通分量。我在这里WA了五发。实在是痛苦。情况一定要考虑好。推荐看这篇博客：https://xiaoxiaoh.blog.csdn.net/article/details/104284558 代码...