No Program No Life

题目链接 题目大意： 判断给你的图是否为强连通图tarjan算法套下就好了 判断强连通分量的数量是否为1#include <bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))const int maxn = 100000 + 10;int head[maxn],cnt;

题目链接 网络流虽然看过，但一直没系统的学过。现在一边复习，一边研究一下。。都是模板题。 二分图匹配。#include <bits/stdc++.h>using namespace std;#define ALL(v) (v).begin(),(v).end()#define cl(a,b) memset(a,b,sizeof(a))#define clr cle

题目链接 hihocoderused数组中保存的就是最小割点集 ans=∑正权值−最小割容量ans = \sum 正权值 - 最小割容量#include <bits/stdc++.h>using namespace std;#define ALL(v) (v).begin(),(v).end()#define cl(a,b) memset(a,b,sizeof(a)

题目链接 hihocoder//#define debug#include <bits/stdc++.h>using namespace std;#define ALL(v) (v).begin(),(v).end()#define cl(a,b) memset(a,b,sizeof(a))#define clr clear()#define pb push_b

在一个有 m×n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。

Alice and Bob play the following game. First, Alice draws some directed graph with N vertices and M arcs. After that Bob tries to destroy it. In a move he may take any vertex of the graph and remove either all

假设一个试题库中有 n n n 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 m m m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

给定正整数序列 x1∼xn ，以下递增子序列均为非严格递增。计算其最长递增子序列的长度 s。计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。如果允许在取出的序列中多次使用 x1 和 xn ，则从给定序列中最多可取出多少个长度为 s 的递增子序列。

假设有来自 n个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri ​​ 。会议餐厅共有 m张餐桌，每张餐桌可容纳 ci个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。

一个餐厅在相继的 n 天里，每天需用的餐巾数不尽相同。假设第 i 天需要 ri ​​ 块餐巾。餐厅可以购买新的餐巾，每块餐巾的费用为 P 分；或者把旧餐巾送到快洗部，洗一块需 M天，其费用为 F 分；或者送到慢洗部，洗一块需 N天，其费用为 S 分（S<F）。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当

某公司发现其研制的一个软件中有 n 个错误，随即为该软件发放了一批共m 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。换句话说，对于每一个补丁 i ，都有 2 个与之相应的错误集合 B1(i) 和 B2(i) ，使得仅当软件包含 B1(i) 中的所有错误，，而不包含 B2(i)

题目链接 51nod上的翻译这种从一个初始状态到达一个目标状态的，从感觉上来说有很多种可能的，可以用网络流。网络流最重要的是建图。 源点与城市的边的容量是a[i]a[i] 城市与汇点的边的容量是b[i]b[i] 城市与自身的边是INFINF，表示可以不移动。 城市与相邻的城市的容量也是INFINF,表示可以移动到相邻的城市。然后跑Dinic求最大流。 如果等于∑a

题目链接一开始看到这题，想的是最大生成树+树链剖分+线段树。时间复杂度大概是O(mlogm+n+nlogn+klogn)O(mlogm+n+nlogn+klogn) 然而貌似是因为线段树的常数大然后炸了。。(不会zkw线段树，待学。orz然后题解说的是最大生成树+倍增法lca 就是创建一个数组 dis[i][j]:=表示i点跟它的第2j个祖先之间路径的最小值dis[i]

题目链接 题目大意： 判断给你的有向图是否为单向连通图用tarjan算法求出强连通分量，以强连通分量为顶点建新图(tarjan算法O(n+m)) 如果一个DAG是单向连通图当且仅当它的拓扑序唯一 也就是说拓扑排序时队列中的元素不能大于1虽然这题点数较小，可以用矩阵，但是前向星可以适应更大的点数#include <cstdio>#include <queue>#in

题目链接 这题跟pat(A)1111很像。。 只是在求最短路和最快的路的次要条件不一样并且输出格式颠倒一下。 之前写过pat(A)1111的代码 就稍微改下。#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;#define

题目链接对每一个垃圾桶都用一遍dijkstra，然后把相应的数据存入结构体排下序，再输出就可以了 如果有一个居民点和垃圾桶间没有路径，这肯定是不行的。#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;#define cl(a,b

题目链接 最快路径其实就是最短路径。以下数组都在满足最短路条件下 num[i] := 表示到达i点的最短路径数 len[i] := 表示到达i点所经过的点数，不包括起点 tot[i] := 表示到达i点所救的人数#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#

题目链接官方题解 题解里面貌似有错 这里应该还有条3->4的边有人会问为什么会有2->4这条边，从图上看2的四个点都被覆盖了。 这就是建图时要注意的地方了，建图时我们只要根据两个矩形是否相交建图就可以了，不必去管矩形的四个点是否被覆盖。 因为虽然2的四个点都被覆盖，但是2是作为1和4之间的关联的。撕1时，会先撕去2，然后再撕去4.所以这里要有条2->4的边。这样在

记下SPFA的两种优化，大牛请无视SPFA算法有两个优化算法 SLF 和 LLL： SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j) < dist(i)，则将j插入队首，否则插入队尾。 LLL：Large Label Last 策略，设队首元素为i，每次弹出时进行判断，队列中所有dist值的平均值为x，若dist(i

题目链接题目大意： 给你n*m的矩阵 ‘W’表示水，其他表示国家 问这些国家最少需要走多少步，才能到达边界与水相邻的国家国家这么多，水就一种，我们不妨反着求。 求从水到这些国家的最短路 这里就有两种算法 一种就是spfa算法 测试了无优化，SLF优化，SLF+LLL优化 实际上这里还是SLF优化快#include <bits/stdc++.h>using n

题目链接题目大意: 给你一个图，判断是欧拉回路，还是不是欧拉回路的欧拉通路，还是不是欧拉图。#include <bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))typedef long long LL;const int INF = 0x3f3f3f3f;const in

题目链接题目大意: 给你n个点树，m个查询 每次查询给出两个点集A,B。 求x∈A,y∈Bx\in A,y\in B 使得lca(x,y)的深度最大lca(x,y)的深度最大倍增lca相关知识 用倍增法处理出lca 然后对每个查询二分深度 处理出A集合的点在二分深度的祖先集合 然后判断B集合里是否存在一个点的祖先在上述集合里#include <bits/stdc

对于LCA有三种算法。 第一种，暴力搜索。 对于数据很小的题可以这样写。 先标记其中一个人的所有祖先，再从第二个人开始往上，向他的父亲搜索，直到搜索到第一个被标记的人，这个人就是他们两个人的最近公共祖先。第二种，基于tarjan的离线算法。是将所有的查询都整理在一起，在去搜索判断，运用并查集找到最近公共祖先。 整理好所有的查询。 从根节点开始搜索。 如果有儿子一直

W 公司有 m 个仓库和 n 个零售商店。第 i 个仓库有 ai 个单位的货物；第 j 个零售商店需要 bj 个单位的货物。货物供需平衡，