怀疑教学内容日渐趋近于宇航员选拔的方向了。
是我的错觉吗。
李超线段树
总之是维护若干条直线/线段的结构。
似乎目前例题比较少，只有两个，不过和DP结合优化的题目应该不会少。
二分图最大匹配
板子请移步P3386，不再赘述。
几个有意思的题目：
CF1139E：
删除边毕竟是不容易的，考虑倒着做来处理，变成加边。
我们可以令二分图左侧为答案（值域），右侧为对应社团。
注意到答案单调不减，因此维护当前答案，每次暴力做匹配，如果找到增广路，答案++，继续以上过程。
由于这样做保证了进行匹配的次数不会很多，所以能过。
注意，有多次进行匹配的情况，访问数组可以与时间戳进行比对，无需在最开始全部赋零以减少复杂度。
#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, m, d, p[N], c[N], timestamp;
int h[N], e[N], ne[N], idx;
int match[N], st[N];
int id[N], unr[N], res[N];
void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
int find(int u)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (st[j] != timestamp)
{
st[j] = timestamp;
if (match[j] == -1 || find(match[j]))
{
match[j] = u;
return 1;
}
}
}
return 0;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)scanf("%d", &p[i]);
for (int i = 1; i <= n; i ++)scanf("%d", &c[i]);
scanf("%d", &d);
for (int i = 1; i <= d; i ++)
{
scanf("%d", &id[i]);
unr[id[i]] = 1;
}
for (int i = 1; i <= n; i ++)
{
if (!unr[i])add(p[i], c[i]);
}
memset(match, -1, sizeof match);
for (int i = d, mex = 0; i; i --)
{
timestamp ++;
while (find(mex))
{
mex ++;
timestamp ++;
}
res[i] = mex;
add(p[id[i]], c[id[i]]);
}
for (int i = 1; i <= d; i ++)printf("%d\n", res[i]);
return 0;
}
CF387D
答案大概是 O(n ^ 3) 级别的，而匹配一次仅仅需要 O(n ^ 2)，因此枚举这个中心点。
最开始统计每个点的出度和入度，注意自环仅仅只计算一次。
对于中心点，需要的答案是 2n – 1 – d_{center}
之后对于非中心点做二分图最大匹配，相当于利用现在所能利用的边。
对于非中心点，需要一个出度，一个入度，大抵长成一个环的样子。
我们设最大匹配的结果是 p。
首先删除无用边的答案是 m – d_{center} – 1 的。
加入新边所需要的答案是 n – 1 – p 的。
然后做完了。
#include<bits/stdc++.h>
using namespace std;
const int N = 505, M = 1005;
int n, m, res = 1e9;
int h[N], e[M], ne[M], idx;
int match[N], st[N], timestamp;
int d[N];
void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
int find(int u, int center)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j != center && st[j] != timestamp)
{
st[j] = timestamp;
if (!match[j] || find(match[j], center))
{
match[j] = u;
return 1;
}
}
}
return 0;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &m);
for (int i = 1, a, b; i <= m; i ++)
{
scanf("%d%d", &a, &b);
add(a, b);
d[a] ++;
if (a != b)d[b] ++;
}
for (int center = 1; center <= n; center ++)
{
int ans = 2 * n - 1 - d[center], matches = 0;
memset(match, 0, sizeof match);
for (int i = 1; i <= n; i ++)
{
if (i != center)
{
timestamp ++;
matches += find(i, center);
}
}
ans += m - d[center] - matches;
ans += (n - 1) - matches;
res = min(res, ans);
}
printf("%d", res);
return 0;
}
二分图最大权匹配
在此之前可以先了解 BFS 进行增广路求解过程。
KM 算法仅仅支持完美匹配，即两侧点数相同。
但是我们可以私自在较小的点集中补点，并自己新建虚边。
整个算法流程通俗理解就是一部分不断降低要求，另一部分不断提高要求，以寻找最大权匹配的过程。
注意此时如果使用 dfs 求增广路，可能出现多次搜索无用边降低效率，复杂度最高高达 O(n ^ 4)。
因此使用 bfs 求。但是我并不知道LUOGU过了为什么HDU上过不了。
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int N = 305;
const int INF = 0x3f3f3f3f;
int n, match[N], pre[N];
int G[N][N], w1[N], w2[N], slack[N];
int st[N];
void bfs(int S)
{
memset(pre, 0, sizeof pre);
memset(st, 0, sizeof st);
memset(slack, 0x3f, sizeof slack);
int cur = 0;
match[cur] = S;
do
{
int d = INF;
int u = match[cur], newcur = 0;
st[cur] = 1;
for (int i = 1; i <= n; i ++)
{
if (st[i])continue;
if (slack[i] > w1[u] + w2[i] - G[u][i])
{
slack[i] = w1[u] + w2[i] - G[u][i];
pre[i] = cur;
}
if (slack[i] < d)
{
d = slack[i];
newcur = i;
}
}
for (int i = 0; i <= n; i ++)
{
if (st[i])
{
w1[match[i]] -= d;
w2[i] += d;
}
else slack[i] -= d;
}
cur = newcur;
}
while (match[cur]);
while (cur)
{
match[cur] = match[pre[cur]];
cur = pre[cur];
}
}
int KM()
{
for (int i = 1; i <= n; i ++)bfs(i);
int res = 0;
for (int i = 1; i <= n; i ++)res += G[match[i]][i];
return res;
}
int main()
{
while(~scanf("%d", &n))
{
memset(match, 0, sizeof match);
memset(w1, 0, sizeof w1);
memset(w2, 0, sizeof w2);
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)scanf("%d", &G[i][j]);
}
printf("%d\n", KM());
}
return 0;
}