牛客练习赛30D(消消乐)

链接：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
思路是从一个未匹配的点开始，沿着未匹配的边走，沿途标记所有的点，对于左侧的未标记的点、右侧标记的点就是选中的最小点覆盖集。