目录
简介
解法
模板题及代码
简介
最小点权覆盖集问题指的是：在图中选取一些点，满足图中每条边连接的两个点中，至少一个被选择，求所选取的点最小权值和。
最大点权独立集问题是最小点权覆盖集问题的对偶问题，指的是：在图中选取一些点，满足：图中每条边连接的两个点中，至多一个被选择，求所选取的点最大权值和。
对于一般图而言，这两个问题是 (NPC) 问题，因此我们着重讨论二分图情况的解法。
解法
因为两个问题是对偶的，所以我们只需解决最小点权覆盖集问题，下为解法：
构建流网络 (G_N)
- 对原图 (G) 二分染色，简便起见，记点的颜色为白点、黑点。
- 建立源点 (s) ，(s) 向白点连接容量为相应点权值的边。
- 类似地，黑点向汇点 (t) 连接容量为相应点权值的边。
- 图中原有的边连接容量为 (∞) 的边。
在流网络 (G_N) 上跑一遍最小割就可以求出答案了。
正确性简证：对于任意一条从 (s) 到 (t) 的路径，一定存在一条边被割断，而且因为原图对应的边容量为 (∞) ，因此割边必然存在于 (s) 与白点之间或者黑点与 (t) 之间，对应的流量便是选取的最小点权。
至于最大点权独立集问题则可以迎刃而解，因为点权覆盖集对于 (G) 的点集 (V) 的补集即为点权独立集，而点集 (V) 的点权之和为常数，所以当点权覆盖集最小时，点权独立集最大，对应的答案即为 (V) 的点权之和减去最小点权覆盖集的点权之和。
模板题及代码
传送门：
最小点权覆盖集问题
https://www.acwing.com/activity/content/problem/content/2649/1/
分析
因为对于每条边，射出这条边的点以及被这条边射入的点至少有一个被选取，因此想到拆点，然后转化为最小点权覆盖集问题。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=205, M=5000+200+10<<1, INF=0x3f3f3f3f;
int n, m, S, T;
struct node{
int to, c, next;
}e[M];
int w[N];
int h[N], tot;
void add(int u, int v, int c){
e[tot].to=v, e[tot].c=c, e[tot].next=h[u], h[u]=tot++;
e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;
}
int q[N], d[N], cur[N];
bool bfs(){
memset(d, -1, sizeof d);
int tt=-1, hh=0;
q[++tt]=S, d[S]=0, cur[S]=h[S];
while(tt>=hh){
int hd=q[hh++];
for(int i=h[hd]; ~i; i=e[i].next){
int go=e[i].to;
if(d[go]==-1 && e[i].c){
d[go]=d[hd]+1;
cur[go]=h[go];
if(go==T) return true;
q[++tt]=go;
}
}
}
return false;
}
int find(int u, int limit){
if(u==T) return limit;
int flow=0;
for(int i=cur[u]; ~i && limit>flow; i=e[i].next){
int go=e[i].to;
cur[u]=i;
if(d[go]==d[u]+1 && e[i].c){
int t=find(go, min(e[i].c, limit-flow));
if(!t) d[go]=-1;
e[i].c-=t, e[i^1].c+=t, flow+=t;
}
}
return flow;
}
int dinic(){
int res=0, flow;
while(bfs()) while(flow=find(S, INF)) res+=flow;
return res;
}
bool vis[N];
void dfs(int u){
vis[u]=true;
for(int i=h[u]; ~i; i=e[i].next){
int go=e[i].to;
if(e[i].c && !vis[go]) dfs(go);
}
}
int main(){
memset(h, -1, sizeof h);
cin>>n>>m;
for(int i=n+1; i<=2*n; i++) cin>>w[i];
for(int i=1; i<=n; i++) cin>>w[i];
S=0, T=2*n+1;
while(m--){
int u, v; cin>>u>>v;
add(u, v+n, INF);
}
for(int i=1; i<=n; i++) add(S, i, w[i]);
for(int i=n+1; i<=2*n; i++) add(i, T, w[i]);
cout<<dinic()<<endl;
dfs(S);
int cnt=0;
for(int i=0; i<tot; i+=2){
int u=e[i^1].to, v=e[i].to;
if(vis[u] && !vis[v]) cnt++;
}
cout<<cnt<<endl;
for(int i=0; i<tot; i+=2){
int u=e[i^1].to, v=e[i].to;
if(vis[u] && !vis[v] && u==S) cout<<v<<' '<<'-'<<endl;
else if(vis[u] && !vis[v] && v==T) cout<<u-n<<' '<<'+'<<endl;
}
return 0;
}
最大点权独立集问题
https://www.acwing.com/activity/content/problem/content/2650/1/
分析
按照格子的行列坐标和的奇偶性将格子染成黑白，构造出一个二分图，将黑白格子看成是黑白点，可知黑白点之间的连边对应的两个点至多选取一个，转化为最大点权独立集问题解决。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=100*100+10, M=4*N+200+10<<1, INF=0x3f3f3f3f;
int n, m, S, T;
struct node{
int to, c, next;
}e[M];
int h[N], tot;
void add(int u, int v, int c){
e[tot].to=v, e[tot].c=c, e[tot].next=h[u], h[u]=tot++;
e[tot].to=u, e[tot].c=0, e[tot].next=h[v], h[v]=tot++;
}
int q[N], d[N], cur[N];
bool bfs(){
memset(d, -1, sizeof d);
int tt=-1, hh=0;
q[++tt]=S, d[S]=0, cur[S]=h[S];
while(tt>=hh){
int hd=q[hh++];
for(int i=h[hd]; ~i; i=e[i].next){
int go=e[i].to;
if(d[go]==-1 && e[i].c){
d[go]=d[hd]+1;
cur[go]=h[go];
if(go==T) return true;
q[++tt]=go;
}
}
}
return false;
}
int find(int u, int limit){
if(u==T) return limit;
int flow=0;
for(int i=cur[u]; ~i && limit>flow; i=e[i].next){
int go=e[i].to;
cur[u]=i;
if(d[go]==d[u]+1 && e[i].c){
int t=find(go, min(e[i].c, limit-flow));
if(!t) d[go]=-1;
e[i].c-=t, e[i^1].c+=t, flow+=t;
}
}
return flow;
}
int dinic(){
int res=0, flow;
while(bfs()) while(flow=find(S, INF)) res+=flow;
return res;
}
int id[105][105], cnt;
int main(){
memset(h, -1, sizeof h);
cin>>n>>m;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) id[i][j]=++cnt;
S=0, T=cnt+1;
int all=0;
int dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
int w; cin>>w; all+=w;
if(i+j&1){
add(S, id[i][j], w);
for(int k=0; k<4; k++){
int kx=i+dx[k], ky=j+dy[k];
if(kx<1 || kx>n || ky<1 || ky>m) continue;
add(id[i][j], id[kx][ky], INF);
}
}else add(id[i][j], T, w);
}
cout<<all-dinic()<<endl;
return 0;
}