网络流，二分、二分图最大匹配
题意：
分析：
这一题出的好啊！！！！正是我能力边缘的题目。有助于提升实力！！！
我们需要插入m段广告，有n+1个空位我们可以插入。当插入时，我们整体得不流畅度可能会改变。
当我们看到max() 时，我们就应该尝试用二分的思想取考虑一下，
a1,a2,a3,a4
当我们将b1插入a1,a2时，这里的不流畅度为：max(abs(a1-b1),abs(a2-b1))
两头稍有特殊。但大致一样。
这就是我们每一条边的代价。
我们很容易想到对着些边权进行二分，将不流畅度大于mid得边都不连。这样我们总体得不流畅度一定小于mid
然后连边，左边是广告，右边是空位。最左边一个超级汇点，最右边一个超级终点。求最大流是不是m
如此，甚好。
(其实这里也就是求一个最大匹配哦)
但是，这是错的！
因为当我们
施行插入时：
a1,a2,a3,a4
b1插入a1,a2时a1,a2局部的不流畅度从abs(a1-a2)变为了max(abs(b1-a1),abs(b1-a2))了
我们忽略了文章原本的不流畅度！！！！
也就是说尽管我们在二分时去掉了所有的bi到空位的权值大于mid的值，但也无法保证最终的不流畅度能够<=mid
另外对于这种情况
A: 1 10 1
B: 9
我们会发现广告的存在反而让我们的文章便流利了。(小Y真是个笨蛋！)
那我们仔细想想吧，我们究竟要建一个怎样的图呢？
我们同样要保证m个广告与每一个空位都有一条边，但同时，我们要保证如果这个空位没有广告占领的话
那么就一定要有一条代表原先不流畅度的边与其连接！
我们在这个途中实行二分，去掉权值大于mid的边，看m个广告能不能全部流出去。
我们可以这样建图：
cap均为1
注意这里的原节点其权值是表示原先的不流畅度。
这号也是与每一个空位对应的！
但是在实行上述的二分操作之前我们还要确定一件事情，就是如何判断处于mid的状态下所有的m个广告都流出了呢？
首先我们要知道，因为对于每一个空位我们都要占领所以最后流出的一定是n+1
关键在于，我们要知道这n+1个空位有没有m个是广告节点占领的而不是原节点占领的！！
此为关键。
若我们直接从S建边连接广告节点和原节点是无法进行区分的！
所以我们可以这样建图：
如此再想让最大流为n+1我们必须让m个广告节点占领空位n+1-m个原节点占领空位了。
然后我们再对边权二分，判断最大流是否为n+1就好了！
代码如下：
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
const int inf = 2e9;
const int max_n = 900;
const int max_m = 200 * 250;
int n, m;
struct edge
{
int to, cap, rev, next;
}E[max_m * 2];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap) {
E[cnt].to = to;
E[cnt].cap = cap;
E[cnt].rev = cnt + 1;
E[cnt].next = head[from];
head[from] = cnt++;
E[cnt].to = from;
E[cnt].cap = 0;
E[cnt].rev = cnt - 1;
E[cnt].next = head[to];
head[to] = cnt++;
}
int iter[max_n];
int dist[max_n];
bool searchpath(int s, int t) {
fill(dist, dist + max_n, -1);
queue<int> que;dist[s] = 0;
que.push(s);
while (!que.empty()) {
int u = que.front();que.pop();
for (int i = head[u];i;i = E[i].next) {
edge& e = E[i];
if (dist[e.to] != -1 || e.cap == 0)continue;
dist[e.to] = dist[u] + 1;
que.push(e.to);
}
}return dist[t] != -1;
}
int matchpath(int u, int t, int f) {
if (u == t)return f;
for (int& i = iter[u];i;i = E[i].next) {
edge& e = E[i];
if (dist[e.to] <= dist[u] || e.cap <= 0)continue;
int d = matchpath(e.to, t, min(e.cap, f));
if (d > 0) {
e.cap -= d;
E[e.rev].cap += d;
return d;
}
}return false;
}
int dinic(int s, int t) {
int flow = 0;int f;
while (searchpath(s, t)) {
for (int i = 1;i < max_n;i++)iter[i] = head[i];
while (f = matchpath(s, t, inf))
flow += f;
}return flow;
}
int a[max_n], b[max_n];
int c[max_n];
int d[max_n][max_n];
void init(int li) {
fill(head, head + max_n, false);
cnt = 1;
int start = 2 * n + m + 3;
int s1 = start + 1, s2 = start + 2;
int ed = s2 + 1;
add(start, s1, m);add(start, s2, n + 1 - m);
for (int i = 1;i <= m;i++)add(s1, i, 1);
for (int i = 1;i <= n + 1;i++)add(s2, i + m, 1);
for (int i = 1;i <= n + 1;i++)add(i + m + n + 1, ed, 1);
for (int j = 1;j <= n + 1;j++)
if (c[j] <= li)
add(j + m, j + m + n + 1, 1);
for (int i = 1;i <= m;i++)
for (int j = 1;j <= n + 1;j++)
if (d[i][j] <= li)
add(i, m + n + 1 + j, 1);
}
bool check(int mid) {
int start = 2 * n + m + 3;
int ed = start + 3;
init(mid);
return dinic(start, ed) == n + 1;
}
int ef(int tot) {
int left = 1;int right = tot;
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid))right = mid;
else left = mid + 1;
}return right;
}
int main() {
ios::sync_with_stdio(0);
int T;cin >> T;
while (T--) {
cin >> n >> m;int tot = 0;
for (int i = 1;i <= n;i++)cin >> a[i];
for (int i = 1;i <= m;i++)cin >> b[i];
for (int i = 2;i <= n;i++) {
c[i] = abs(a[i] - a[i - 1]);
tot = max(tot, c[i]);
}c[1] = 0;c[n + 1] = 0;
for (int i = 1;i <= m;i++) {
d[i][1] = abs(b[i] - a[1]);
d[i][n + 1] = abs(b[i] - a[n]);
tot = max(tot, max(d[i][1], d[i][n + 1]));
for (int j = 2;j <= n;j++) {
d[i][j] = max(abs(b[i] - a[j]), abs(b[i] - a[j - 1]));
tot = max(tot, d[i][j]);
}
}cout << ef(tot) << endl;
}
}二分图做法：
还记得我上面说的吗，对于第一个那个我们建错的图，我说其实我们在实现一个最大匹配。
那么对于我们最后的图呢？
其实每一次check时我们检查最大流是否为n+1时，其实也是正在进行最大匹配！！！！
只不过我们这里的最大匹配有些不一样？！
再看这张图：
这里的最大匹配其实是，我们要在左边前m个点绝对被匹配到的前提下，进行左边后n+1个点的最大匹配。
最后总最大匹配要等于n+1我们check()才return true
那么困难就是如何保证前m个一定被匹配到呢？
这里需要对最大匹配算法： 匈牙利算法，HK算法 其实现原理进行理解！！
如果你尚不明白匈牙利算法或者HK算法的实现原理，这里给你传送门：
匈牙利算法：https://blog.csdn.net/dengheCSDN/article/details/77619308?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param
HK算法：https://my.oschina.net/u/4363748/blog/4220057/print
稍微理解一下，就好了。
我们先来看匈牙利：
关键在于其matchpath的部分
bool match(int i)
{
for (int j = 1; j <= N; ++j)
if (Map[i][j] && !vis[j]) //有边且未访问
{
vis[j] = true; //记录状态为访问过
if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
{
p[j] = i; //当前左侧元素成为当前右侧元素的新匹配
return true; //返回匹配成功
}
}
return false; //循环结束，仍未找到匹配，返回匹配失败
}我们看着一小部分：
if (p[j] == 0 || match(p[j])) //如果暂无匹配，或者原来匹配的左侧元素可以找到新的匹配
{
p[j] = i; //当前左侧元素成为当前右侧元素的新匹配
return true; //返回匹配成功
}注意当前左侧成为右侧元素的新匹配！注意，这里我们不是吧当前match的节点去和找到的未匹配的右半部分节点连接
而是直接从人家手里抢走他匹配的节点，然后让人家再去抢别人的 老婆 节点。最后被抢的那个人再去和那个我们找到的尚未名花有主的右节点匹配。而如果我们发现最后一个人找不到未匹配的右节点，那么我们就不会去抢别人的老婆！
即，如果我们当前节点的匹配会使之前匹配过的节点不匹配，那么我们就放弃当前节点的匹配！！
再看看我们的问题：在前m个节点一定被匹配的情况下，求最大匹配。
很简单了，我们只要按顺序先去匹配前m和节点就可以了，反正后面匹配的节点也不会对前面匹配的节点造成破坏。
大可高枕无忧！我们唯一要做的就是在匹配前m个节点时遇到无法匹配的情况时，return false
原匈牙利算法(不写matchpath了)
int Hungarian(){
int cnt = 0;
for (int i = 1; i <= M; ++i){
memset(vis, 0, sizeof(vis)); //重置vis数组
if (match(i))
cnt++;
}
return cnt;
}只要稍微改改
int Hungarian() {
int cnt = 0;
for (int i = 1; i <= N; ++i) {
memset(vis, 0, sizeof(vis)); //重置vis数组
if (!match(i)) {
if (i <= m)
return false;
}
else cnt++;
}
return cnt;
}这就成了！！！
最大流算法dinic复杂度为O(V^2|E|)
匈牙利算法复杂度为O(V|E|)
可喜可贺，可喜可贺！！你试试，我想会变得快很多。
但真正快的还属HK算法！
我知道HK算法理解是有困难的，但请你看看HK算法的matchpath函数：
bool matchpath(int u) {
for (int i = head[u];i;i = E[i].next) {
int v = E[i].to;
if (distleft[v] != distright[u] + 1)continue;
if (distleft[v] == dist && leftTo[v] != -1)continue;
distleft[v] = -1;
if (leftTo[v] == -1 || matchpath(leftTo[v])) {
rightTo[u] = v;leftTo[v] = u;
return true;
}
}return false;
}和匈牙利算法一样这里：
if (leftTo[v] == -1 || matchpath(leftTo[v])) {
rightTo[u] = v;leftTo[v] = u;
return true;
}你会发现他也遵循同样的原则：
如果当前节点的匹配，会使之前匹配过的节点不匹配，那么我将不再匹配！！
那么我们同样只要保证我们先匹配前m个节点就好了嘛！
原HK算法(我就不写match和search了，直接些主函数)
int HK() {
fill(rightTo, rightTo + 1 + N, -1);
fill(leftTo, leftTo + 1 + N, -1);
int ans = 0;
while (searchpath()) {
for (int i = 1;i <= N;i++) {
if (rightTo[i] == -1 && matchpath(i))
ans++;
}
}return ans;
}改改，让他先匹配前m个，再匹配后n+1个：
int HK() {
fill(rightTo, rightTo + 1 + n + 1 + m, -1);
fill(leftTo, leftTo + 1 + n + 1 + m, -1);
int ans = 0;
while (searchpath(m)) {
for (int i = 1;i <= m;i++) {
if (rightTo[i] == -1 && matchpath(i))
ans++;
}
}if (ans < m)return ans;
while (searchpath(m + n + 1)) {
for (int i = 1;i <= n + 1 + m;i++) {
if (rightTo[i] == -1 && matchpath(i))
ans++;
}
}
return ans;
}如此，甚好！
HK算法的复杂度为O(N^0.5|E|)
进化之路：
O(N^2|E|) -> O(N|E|) -> O(N^0.5|E|) -> O(1)
提交后你会发现所需时间会有质的飞跃
这里就不给匈牙利算法的了，直接给HK算法了，其实就是换个函数而已罢了
##代码如下：
#include<iostream>
#include<queue>
using namespace std;
const int inf = 2e9;
const int max_n = 500;
const int max_m = 200 * 200;
int n, m;
struct edge
{
int to,next;
}E[max_m * 2];
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 rightTo[max_n], leftTo[max_n];
int distright[max_n], distleft[max_n];
int dist;
bool searchpath(int tot) {
fill(distright, distright + 1 + tot, -1);
fill(distleft, distleft + 1 + n + m + 1, -1);
queue<int> que;dist = inf;
for (int i = 1;i <= tot;i++)
if (rightTo[i] == -1)
que.push(i);
while (!que.empty()) {
int u = que.front();que.pop();
if (distright[u] > dist)break;
for (int i = head[u];i;i = E[i].next) {
int v = E[i].to;
if (distleft[v] != -1)continue;
distleft[v] = distright[u] + 1;
if (leftTo[v] == -1)dist = distleft[v];
else {
distright[leftTo[v]] = distleft[v] + 1;
que.push(leftTo[v]);
}
}
}return dist != inf;
}
bool matchpath(int u) {
for (int i = head[u];i;i = E[i].next) {
int v = E[i].to;
if (distleft[v] != distright[u] + 1)continue;
if (distleft[v] == dist && leftTo[v] != -1)continue;
distleft[v] = -1;
if (leftTo[v] == -1 || matchpath(leftTo[v])) {
rightTo[u] = v;leftTo[v] = u;
return true;
}
}return false;
}
int HK() {
fill(rightTo, rightTo + 1 + n + 1 + m, -1);
fill(leftTo, leftTo + 1 + n + 1 + m, -1);
int ans = 0;
while (searchpath(m)) {
for (int i = 1;i <= m;i++) {
if (rightTo[i] == -1 && matchpath(i))
ans++;
}
}if (ans < m)return ans;
while (searchpath(m + n + 1)) {
for (int i = 1;i <= n + 1 + m;i++) {
if (rightTo[i] == -1 && matchpath(i))
ans++;
}
}
return ans;
}
int a[max_n], b[max_n];
int c[max_n];
int d[max_n][max_n];
void init(int li) {
fill(head, head + max_n, false);
cnt = 1;
for (int i = 1;i <= m;i++)
for (int j = 1;j <= n + 1;j++)
if (d[i][j] <= li)
add(i,j);
for (int i = 1;i <= n + 1;i++)
if (c[i] <= li)
add(i + m, i);
}
bool check(int mid) {
init(mid);
return HK() == n + 1;
}
int ef(int tot) {
int left = 1;int right = tot;
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid))right = mid;
else left = mid + 1;
}return right;
}
int main() {
ios::sync_with_stdio(0);
int T;cin >> T;
while (T--) {
cin >> n >> m;int tot = 0;
for (int i = 1;i <= n;i++)cin >> a[i];
for (int i = 1;i <= m;i++)cin >> b[i];
for (int i = 2;i <= n;i++) {
c[i] = abs(a[i] - a[i - 1]);
tot = max(tot, c[i]);
}c[1] = 0;c[n + 1] = 0;
for (int i = 1;i <= m;i++) {
d[i][1] = abs(b[i] - a[1]);
d[i][n + 1] = abs(b[i] - a[n]);
tot = max(tot, max(d[i][1], d[i][n + 1]));
for (int j = 2;j <= n;j++) {
d[i][j] = max(abs(b[i] - a[j]), abs(b[i] - a[j - 1]));
tot = max(tot, d[i][j]);
}
}
cout << ef(tot) << endl;
}
}好题！好题！
京公网安备 11010502036488号