斜率dp 第一道斜率dp题，终于是理解了斜率dp。点亮技能树，我会变的越来越强的！！ #include<iostream> #include<algorithm> #include<deque> using namespace std; const int max_n = 5e5+100; typedef long long ll; int n,M; ll a[max_n]; ll sum[max_n]; deque<int> que; ll dp[max_n]; bool check(ll k){ int a = que[0],b=qu...

没做出来，上网看人家的题解后终于明白了。其实做的时候也发觉了，这应该是一道差分题。但是究竟应该如何差分呢？对什么进行差分呢？搞不明白。在这道题中，我们可以O(n^2)的计算出所有的一个区间的覆盖。但是，两个区间的话怎么比较他们的最大值呢？总不能O(m)的一一对照吧！那样的话就O(n^2m)不行！所以该怎么办呢？看了大佬的博客，发现大佬维护了这么一个东西sub[i][j]意为：有两个k区间一个是以i为开头一个是以j为开头以i为开头的区间因为以j为开头的区间而减去的贡献。为什么要维护这个东西呢？因为事实上，在我们计算m中每一个区间对当前k区间的贡献度的时候，我们是可以计算出比此时贡献度小的k区间在...

这里学到的是一个输出最小割的方案！！！在跑完最大流后，属于最小割的边肯定cap都为零了。我们再以源点为起点进行dfs搜索，标记。然后最小割会将其阻拦住，然后我们再遍历边，看有哪些边一端被标记了另一端没有被标记。这样就好了。 #include<iostream> #include<algorithm> #include<set> using namespace std; typedef pair<int,int> pii; const int max_n = 100; const int max_m = 1000; const int inf = ...

我们发现，对于一个有向图，他若是形成了一个换。那么我们把他拆点，成二分图。会发现这个二分图一定会形成一个完备匹配。那么这题就明了了。我们建立二分图，其中边的权值取负数，然后跑一遍KM就可以了。我邻接表用多了，没怎么用邻接矩阵。这里刚开始忘给矩阵付初始的值-inf了。。。。。。 代码如下 #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int max_n = 250; const int inf =...

没什么难的，不难看出这是求最小割。关键是解决点权问题。我们可以拆点，拆成in和out然后连边权值为cost 之后的边正常连，只不过权值都为inf代表不可以割这里的边。 然后跑个最大流就好了。 #include<iostream> #include<algorithm> using namespace std; const int max_n = 500; const int max_m = 20500; const int inf = 1e9; struct edge { int to,cap,next; }E[max_m<<2]; int n; i...

关键在于建图，食物放左边，饮料放右边，人员放中间。需要注意的是，人员要拆点，保证一人只能吃一份。以后都不用dinic了，都用ISAP #include<iostream> #include<algorithm> using namespace std; const int max_n = 900; const int max_m = max_n*max_n; const int inf=0x3f3f3f3f; struct edge { int to,cap,next; }E[max_m<<2]; int n; int head[max_n],cnt...

淦，竟然卡dinic给出IASP的模板： #include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; typedef long long ll; const int max_n=100050; const int max_m=200050; const int inf=0x3f3f3f3f; struct edge { int to,cap,next; }E[max_m<<2]; int n,m; i...

板子题，学了个带花树算法。时间复杂度O(n^3)用于求一般图的最大匹配，即有奇环的图。 struct edge{ int to,next; }E[max_m<<1]; int head[max_n]; int cnt=1; void add(int from,int to){ E[cnt].to=to; E[cnt].next=head[from]; head[from]=cnt++; } int par[max_n],pre[max_n],link[max_n],ans; deque<int> q; char ty[max_n]; in...

竟然卡最小费用最大流。因为是稠密图的原因吗？那我们呢就用KM算法吧。这一用不要紧，我竟然发现我的KM模板竟然也被卡时间了。。。。。。赶紧更新自己的模板。 #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; typedef pair<int,int> pii; const int max_n = 1000; const int max_m = 1200; const int inf = 1e9; int...

floyd+多重匹配+二分 先使用floyd求得最短距离我们二分答案，然后跑多重匹配就好了。 #include<iostream> #include<algorithm> #include<vector> using namespace std; const int max_n = 300; const int max_m = 1e5; const int inf = 1e9; int k,c,m; int g[max_n][max_n]; struct edge{ int to,next; }E[max_m<<1]; int head[...

想法都是二分答案。我的想法是跑网络流，建图。还有一种想法是，多重匹配。即在匹配时增加匹配数的判断。这是很有趣的。solution2是多重匹配的匈牙利算法。注意，我用HK算法实现多重匹配时发现非常慢！！！！所以建议用匈牙利！solution1： #include<iostream> #include<algorithm> #include<queue> #include<vector> using namespace std; const int max_n = 5000; const int max_m = 1e6; const int inf ...

真的是很巧妙的建边。我刚开始就想着猫和狗了。但事实上我们应该把小孩子当作节点，相互冲突的小孩连上边然后求最大独立集 真的女少口阿 我们事实上建造的是一个有向图，对一个有向图求解最大匹配。因为这里我们没有将整个图分为左右节点所以我选择的是匈牙利算法而不是hk算法。其实我想用hk算法的，但是我没有在不分图的情况下的hk惨。。。 #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<cstring> using namespace s...

最小不可相交路径覆盖。 点数-最大匹配数 代码如下： #include<iostream> #include<algorithm> #include<queue> using namespace std; const int max_n = 2000; const int inf = 2e9; struct edge{ int to,next; }E[max_n<<1]; int head[max_n]; int cnt=1; void add(int from,int to){ E[cnt].to=to;E[cnt].next=...

我又回来了！！！！ 这是典型的求最小可相交路径覆盖我们先求闭包，利用闭包连边，然后求解最小不可相交路径就可以了。什么？如何求解最小不可相交路径覆盖？点数-最大匹配数 代码如下： #include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int max_n = 550; const int inf = 2e9; struct edge{ int to,next; }E[max_n*max_n*max_...