最小路径点覆盖
在一张 DAG 上，求一个路径的集合，使得它们两两不相交，且覆盖所有的点。
结论：答案即为 \(总点数-最大匹配\)（于是 \(总点数-最大匹配=总点数-最小点覆盖=最大独立集=最大团=最小路径点覆盖\)）。
证明：
不妨转换角度，从研究路径转为研究点。
因为路径两两不交，所以每条路径都会有一个唯一的终点。
因为 DAG 不一定是一张二分图，于是我们将其拆成二分图。
具体的，我们将每个点拆成入点（左部点）和出点（右部点），因为入点和出点自己内部没有连边，所以这一定是一张二分图。
我们知道终点一定没有出边，于是没有匹配的右部点就是终点。
我们要使路径数量最少，那么终点就要最少，于是匹配就得最多，这不就是最大匹配吗，而且它的不共点性质也帮我们处理了不相交的问题。
证毕。
P2764
模板。
code
#include<bits/stdc++.h>
using namespace std;
const int N=4e2+5;
int n,m,idx,ans;
vector<int> G[N];
int vis[N],match[N];
bool out[N];
bool hungary(int cur){
if(vis[cur]==idx){
return 0;
}
vis[cur]=idx;
for(int i:G[cur]){
if(!match[i]||hungary(match[i])){
match[i]=cur;
out[cur]=1;
return 1;
}
}
return 0;
}
void print(int cur){
if(!match[cur+n]){
cout<<cur<<' ';
return;
}
print(match[cur+n]);
cout<<cur<<' ';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G[u].push_back(v+n);
}
for(int i=1;i<=n;i++){
idx++;
if(hungary(i))
ans++;
}
for(int i=1;i<=n;i++)
if(!out[i])
print(i),cout<<'\n';
cout<<n-ans;
return 0;
}
UVA1201
将每个乘客看作点，如果送完某个乘客后能赶到另一个乘客那里去，则将它们俩建边，形成了一个 DAG。将每个出租车司机的工作流程看作路径，显然两个出租车司机不能同时接一个乘客（不相交）且必须送完所有乘客（覆盖所有的点），直接上最小路径点覆盖即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int t,n,m,idx,ans;
vector<int> G[N];
int vis[N],match[N];
bool out[N];
struct GUEST{
int sta,sx,sy,ex,ey;
}g[N];
bool hungary(int cur){
if(vis[cur]==idx){
return 0;
}
vis[cur]=idx;
for(int i:G[cur]){
if(!match[i]||hungary(match[i])){
match[i]=cur;
out[cur]=1;
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while(t--){
for(int i=1;i<=n;i++)
G[i].clear();
cin>>n;
for(int i=1;i<=n;i++){
string s;
int sx,sy,ex,ey;
cin>>s>>g[i].sx>>g[i].sy>>g[i].ex>>g[i].ey;
g[i].sta=((s[0]-'0')*10+(s[1]-'0'))*60+((s[3]-'0')*10+(s[4]-'0'));
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j){
int ii=i,jj=j;
if(g[ii].sta>g[jj].sta)
swap(ii,jj);
if(abs(g[ii].sx-g[ii].ex)+abs(g[ii].sy-g[ii].ey)+abs(g[jj].sx-g[ii].ex)+abs(g[jj].sy-g[ii].ey)<g[jj].sta-g[ii].sta)
G[ii].push_back(jj);
}
}
}
ans=idx=0;
memset(vis,0,sizeof vis);
memset(match,0,sizeof match);
for(int i=1;i<=n;i++){
idx++;
if(hungary(i))
ans++;
}
cout<<n-ans<<'\n';
}
return 0;
}
OpenJ_Bailian-1548
这题没说路径不相交，但是不相交一定不劣。
然后就变成典题了，不再详细分析。
code
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,m,idx,ans;
int id[N][N];
pair<int,int> p[N*N];
vector<int> G[N*N*2];
int vis[N*N*2],match[N*N*2];
bool hungary(int cur){
if(vis[cur]==idx){
return 0;
}
vis[cur]=idx;
for(int i:G[cur]){
if(!match[i]||hungary(match[i])){
match[i]=cur;
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tx,ty;
while(cin>>tx>>ty&&(tx!=-1||ty!=-1)){
memset(id,0,sizeof id);
n=0;
id[tx][ty]=++n;
p[n]={tx,ty};
while(cin>>tx>>ty&&(tx||ty)){
id[tx][ty]=++n;
p[n]={tx,ty};
}
for(int i=1;i<=N*N;i++)
G[i].clear();
for(int i=1;i<=n;i++){
for(int j=p[i].first;j<N;j++){
for(int k=p[i].second;k<N;k++){
if(j==p[i].first&&k==p[i].second)
continue;
if(id[j][k]){
G[id[p[i].first][p[i].second]].push_back(id[j][k]);
break;
}
}
}
}
ans=idx=0;
memset(vis,0,sizeof vis);
memset(match,0,sizeof match);
for(int i=1;i<=n;i++){
idx++;
if(hungary(i))
ans++;
}
cout<<n-ans<<'\n';
}
return 0;
}
HDU-3861
红色字体部分出现了很明显的强连通分量迹象，直接缩成 DAG。
对于一个 DAG，我们要求一个子图里的任意两点都是弱连通的，画一下图就会发现只有链可以满足这个条件，然后就变成典题了。
属于是板子拼接题了哈哈哈（唐诗题是这样的）。
code
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
using namespace std;
const int N=5e3+5,M=1e5+5;
int t,n,m;
int cnt,tot,idx,ans;
int dfn[N],low[N],instk[N],scc[N];
stack<int> s;
pair<int,int> p[N];
vector<int> G[N],T[N];
int vis[N],match[N];
struct EDGE{
int u,v;
}e[M];
void tarjan(int v){
s.push(v),instk[v]=1,dfn[v]=low[v]=++cnt;
for(int i:G[v]){
if(!dfn[i])
tarjan(i),low[v]=min(low[v],low[i]);
else if(instk[i])
low[v]=min(low[v],dfn[i]);
}
if(dfn[v]==low[v]){
++tot;
for(;s.top()!=v;s.pop())
instk[s.top()]=0,scc[s.top()]=tot;
instk[v]=0,scc[v]=tot,s.pop();
}
}
bool hungary(int cur){
if(vis[cur]==idx){
return 0;
}
vis[cur]=idx;
for(int i:T[cur]){
if(!match[i]||hungary(match[i])){
match[i]=cur;
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while(t--){
for(int i=1;i<=n;i++)
G[i].clear(),T[i].clear();
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G[u].push_back(v);
e[i]={u,v};
}
cnt=tot=0;
while(!s.empty())
s.pop();
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(instk,0,sizeof instk);
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=m;i++)
if(scc[e[i].u]!=scc[e[i].v])
T[scc[e[i].u]].push_back(scc[e[i].v]);
ans=idx=0;
memset(vis,0,sizeof vis);
memset(match,0,sizeof match);
for(int i=1;i<=tot;i++){
idx++;
if(hungary(i))
ans++;
}
cout<<tot-ans<<'\n';
}
return 0;
}
有相交的最小路径点覆盖
很简单，如图：
在这张图中，不相交的最小路径点覆盖的答案为 \(3\)，而相交的答案为 \(2\)，区别在于 \(4,5\) 两个节点是否在一条路径上。
实际上，我们仅仅关心路径数量而非方案（大多数情况下），于是我们直接将 \(4,5\) 连边即可转化为不相交的情形。
将其加以推广，我们仅需跑传递闭包得知所有直接或间接连通的点对，然后将它们之间加边使其全部转化为直接连通即可跑不相交的最小路径点覆盖。
P10938
板子。
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e2+5,M=3e4+5;
int n,m,idx,ans;
int dis[N][N];
vector<int> G[N],T[N];
int vis[N],match[N];
void floyd(){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]|=dis[i][k]&dis[k][j];
}
bool hungary(int cur){
if(vis[cur]==idx){
return 0;
}
vis[cur]=idx;
for(int i:T[cur]){
if(!match[i]||hungary(match[i])){
match[i]=cur;
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G[u].push_back(v);
dis[u][v]=1;
}
floyd();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis[i][j])
T[i].push_back(j);
for(int i=1;i<=n;i++){
idx++;
if(hungary(i))
ans++;
}
cout<<n-ans<<'\n';
return 0;
}
OpenJ_Bailian-3473
有点诈骗吧。本来以为给了个邻接矩阵，以为是相交的，结果是不相交的。
其实和 UVA1201 一致，只是不同街区的行走需要求一个最短路。
code
#include<bits/stdc++.h>
using namespace std;
const int Q=31,M=2e2+5;
int q,m;
int idx,ans;
int vis[M],match[M];
int dis[Q][Q];
struct TASK{
int p,t,d;
}task[M];
vector<int> G[M];
void floyd(){
for(int k=1;k<=q;k++)
for(int i=1;i<=q;i++)
for(int j=1;j<=q;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
bool hungary(int cur){
if(vis[cur]==idx){
return 0;
}
vis[cur]=idx;
for(int i:G[cur]){
if(!match[i]||hungary(match[i])){
match[i]=cur;
return 1;
}
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
while(cin>>q>>m){
if(!q&&!m)
break;
for(int i=1;i<=q;i++){
for(int j=1;j<=q;j++){
cin>>dis[i][j];
dis[i][j]=(dis[i][j]==-1?0x3f3f3f3f:dis[i][j]);
}
}
for(int i=1;i<=m;i++)
cin>>task[i].p>>task[i].t>>task[i].d,G[i].clear();
floyd();
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
if(i!=j&&task[i].t+task[i].d+dis[task[i].p][task[j].p]<=task[j].t)
G[i].push_back(j);
ans=idx=0;
memset(vis,0,sizeof vis);
memset(match,0,sizeof match);
for(int i=1;i<=m;i++){
idx++;
if(hungary(i))
ans++;
}
cout<<m-ans<<'\n';
}
return 0;
}
总结：
-
图论题想不明白时画图。
-
注意题中关键信息（解读条件）。
-
注意最小路径点覆盖问题区分相交 / 不相交，以及它和其他问题之间的关系（上文已给出）。