链接：https://ac.nowcoder.com/acm/contest/216/D
思路：一道比较经典的网络流题目，按行和列建图，对于每一个a[i][j]='*'的点，我们从i向j拉一条边，那么原问题可以转换为，在行和列对应的二分图中，每一条边至少要有一个端点被选中，求最小点覆盖。由定理可知，最小点覆盖的值定于最大匹配数，如果用网络流的话也就是最大流。这个题难点在于方案输出，我们对于两种算法的方案输出解释一下：
网络流
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 6000;
const int INF = 1e9;
struct edge{
int from,to,cap,flow;
};
struct Dinic{
int n,m,s,t;
vector<edge> edges;
vector<int> G[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn];
void init(int n){
this->n = n;
edges.clear();
for(int i=0;i<=n;i++)G[i].clear();
}
void addedge(int from,int to,int cap){
edges.push_back(edge{from,to,cap,0});
edges.push_back(edge{to,from,0,0});
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool bfs(){
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(s);
d[s] = 0;
vis[s] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
for(int i=0;i<G[x].size();i++){
edge &e = edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow){
vis[e.to] = 1;
d[e.to] = d[x] + 1;
q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int a){
if(x==t||a==0)return a;
int flow = 0,f;
for(int &i = cur[x];i<G[x].size();i++){
edge &e = edges[G[x][i]];
if(d[x] + 1 == d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
e.flow+=f;
edges[G[x][i]^1].flow -=f;
flow+=f;
a-=f;
if(a==0){
break;
}
}
}
return flow;
}
int maxflow(int s,int t){
this->s = s;
this->t = t;
int flow = 0;
while(bfs()){
memset(cur,0,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}
}solver;
int iscut[maxn];
void dfs(int u){
iscut[u] = 1;
for(int i=0;i<solver.G[u].size();i++){
edge e = solver.edges[solver.G[u][i]];
if(!iscut[e.to]&&e.cap>e.flow)dfs(e.to);//注意网络流中的写法
}
}
char ch[2010];
int main(){
scanf("%d%d",&n,&m);
solver.init(n+m+2);
for(int i=1;i<=n;i++){
solver.addedge(0,i,1);
scanf("%s",ch);
for(int j=0;j<m;j++){
if(ch[j]=='*')solver.addedge(i,j+1+n,1e9);
}
}
for(int i=1;i<=m;i++)solver.addedge(n+i,n+m+1,1);
int res = solver.maxflow(0,n+m+1);
dfs(0);
printf("%d\n",res);
int l = 0,r = 0;
for(int i=1;i<=n;i++){
if(!iscut[i])l++;
}
for(int i=n+1;i<=n+m;i++){
if(iscut[i])r++;
}
printf("%d ",l);
for(int i=1;i<=n;i++){
if(!iscut[i])printf("%d ",i);
}
printf("\n%d ",r);
for(int i=n+1;i<=n+m;i++){
if(iscut[i])printf("%d ",i-n);
}
printf("\n");
return 0;
}
匈牙利算法：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 4010;
//注意编号从1开始
vector<int> G[maxn];
bool vis[maxn];
int link[maxn];
int m;
int nx,ny;
void init(int nx,int ny){
for(int i=0;i<=nx+ny;i++)G[i].clear();
}
inline void addedge(int from,int to){
G[from].push_back(to);
}
bool dfs(int u){
vis[u] = 1;
for(int i=0;i<G[u].size();i++){
int v = G[u][i];
if(!vis[v]){
vis[v] = 1;
if(link[v]==-1||dfs(link[v])){
link[v] = u;
link[u] = v;
return true;
}
}
}
return false;
}
int hungrey(){
int res = 0;
memset(link,-1,sizeof(link));
for(int i=1;i<=nx;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))res++;
}
return res;
}
char a[maxn][maxn];
int main(){
scanf("%d%d",&nx,&ny);
init(nx,ny);
for(int i=1;i<=nx;i++){
scanf("%s",a[i]+1);
for(int j=1;j<=ny;j++){
if(a[i][j]=='*')addedge(i,j+nx);
}
}
int res = hungrey();
printf("%d\n",res);
memset(vis,0,sizeof(vis));//记得先清空已经用过的标记
for(int i=1;i<=nx;i++){
if(link[i]==-1)dfs(i);
}
int ans = 0;
for(int i=1;i<=nx;i++){
if(!vis[i])ans++;
}
printf("%d ",ans);
for(int i=1;i<=nx;i++){
if(!vis[i])printf("%d ",i);
}
ans = 0;
for(int i=nx+1;i<=nx+ny;i++){
if(vis[i])ans++;
}
printf("\n%d ",ans);
for(int i=nx+1;i<=nx+ny;i++){
if(vis[i])printf("%d ",i-nx);
}
printf("\n");
return 0;
}
关于求解最小点覆盖集，可以参考如下：
https://blog.csdn.net/niushuai666/article/details/7036897
思路是从一个未匹配的点开始，沿着未匹配的边走，沿途标记所有的点，对于左侧的未标记的点、右侧标记的点就是选中的最小点覆盖集。
网友评论