金牌导航-二分图匹配

例题A题解

将行和列相匹配，跑最小割即可。

例题A代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e3 + 10, maxm = 1e6 + 10,INF = 0x3f3f3f3f;

int n, m;

int head[maxn], tot = 1;
struct edge{
    int to, nexte, cap, flow;
    edge(int to = 0,int ne = 0,int ca = 0,int fl = 0):to(to),nexte(ne),cap(ca),flow(fl){}
}e[maxm];
void add(int u,int v,int cap){e[++tot] = edge(v,head[u],cap);head[u] = tot;}
void addd(int u,int v,int cap){add(u,v,cap);add(v, u, 0);}

int dep[maxn], cur[maxn];
int dfs(int u,int flow,int T){
    // printf("%lld\n",u);
    if(u == T)return flow;
    int rest = 0, tmp = 0;
    for(int i = cur[u];i && flow;i = e[i].nexte){
        cur[u] = i; int v = e[i].to;
        if(e[i].cap - e[i].flow > 0 && (dep[v] == dep[u] + 1)){
            tmp = dfs(v,min(flow,e[i].cap - e[i].flow),T);
            if(tmp == 0)dep[v] = INF;
            e[i].flow += tmp; e[i ^ 1].flow -= tmp;
            flow -= tmp;rest += tmp;
            if(!flow)return rest;
        }
    }
    return rest;
}
bool bfs(int S,int T){
    queue<int> que;
    for(int i = 1;i <= T;i++){dep[i] = INF;cur[i] = 0;}
    que.push(S);dep[S] = 1; cur[S] = head[S];
    while(!que.empty()){
        int u = que.front(); que.pop();
        for(int i = head[u];i;i = e[i].nexte){
            int v = e[i].to;
            if(e[i].cap - e[i].flow > 0 && dep[v] == INF){
                que.push(v);
                cur[v] = head[v];
                dep[v] = dep[u] + 1;
                if(v == T)return 1;
            }
        }
    }
    return 0;
}
int Dinic(int S,int T){
    int mxflow = 0;
    while(bfs(S,T)){mxflow += dfs(S,INF,T);}
    return mxflow;
}

signed main(){
    n = read(); m = read();
    int S = n * 2 + 1, T = n * 2 + 2;
    for(int i = 1;i <= m;i++){
        int u = read(), v = read();
        addd(u, v + n, INF);
    }
    for(int i = 1;i <= n;i++){addd(S,i,1);addd(i + n,T,1);}
    printf("%d\n",Dinic(S,T));
    return 0;
}

例题B题解

老套路，将整个地图按照坐标和奇偶性黑白染色，然后从白点向黑点连边，特别的，不能选择的点不连边。然后跑二分图最大匹配，最大点独立集就是答案。

例题B代码

#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10, maxm = 1e6 + 10,INF = 0x3f3f3f3f;

int n;

int head[maxn], tot = 1;
struct edge{
    int to, nexte, cap, flow;
    edge(int to = 0,int ne = 0,int ca = 0,int fl = 0):to(to),nexte(ne),cap(ca),flow(fl){}
}e[maxm];
void add(int u,int v,int cap){e[++tot] = edge(v,head[u],cap);head[u] = tot;}
void addd(int u,int v,int cap){add(u,v,cap);add(v, u, 0);}

int dep[maxn], cur[maxn];
int dfs(int u,int flow,int T){
    // printf("%lld\n",u);
    if(u == T)return flow;
    int rest = 0, tmp = 0;
    for(int i = cur[u];i && flow;i = e[i].nexte){
        cur[u] = i; int v = e[i].to;
        if(e[i].cap - e[i].flow > 0 && (dep[v] == dep[u] + 1)){
            tmp = dfs(v,min(flow,e[i].cap - e[i].flow),T);
            if(tmp == 0)dep[v] = INF;
            e[i].flow += tmp; e[i ^ 1].flow -= tmp;
            flow -= tmp;rest += tmp;
            if(!flow)return rest;
        }
    }
    return rest;
}
bool bfs(int S,int T){
    queue<int> que;
    for(int i = 1;i <= T;i++){dep[i] = INF;cur[i] = 0;}
    que.push(S);dep[S] = 1; cur[S] = head[S];
    while(!que.empty()){
        int u = que.front(); que.pop();
        for(int i = head[u];i;i = e[i].nexte){
            int v = e[i].to;
            if(e[i].cap - e[i].flow > 0 && dep[v] == INF){
                que.push(v);
                cur[v] = head[v];
                dep[v] = dep[u] + 1;
                if(v == T)return 1;
            }
        }
    }
    return 0;
}
int Dinic(int S,int T){
    int mxflow = 0;
    while(bfs(S,T)){mxflow += dfs(S,INF,T);}
    return mxflow;
}

int getid(int x,int y){
    if(x < 1 || y < 1 || x > n || y > n)return -1;
    return x * n + y;
}

int mp[600][600];
const int dx[8] = {-2,-1, 1, 2, 2, 1,-1,-2};
const int dy[8] = {-1,-2,-2,-1, 1, 2, 2, 1};

char ch[600];

signed main(){
    n = read();int cnt = n * n;
    int S = n * n + n + 1, T = n * n + n + 2;
    for(int i = 1;i <= n;i++){
        scanf("%s",ch + 1);
        for(int j = 1;j <= n;j++)
            cnt -= (mp[i][j] = ch[j] - '0');
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if((((i + j) & 1) == 0) && !mp[i][j]){
                int u = getid(i,j);addd(S,u,1);
                for(int k = 0;k < 8;k++){
                    int nx = i + dx[k], ny = j + dy[k];
                    int v = getid(nx,ny);
                    if(v == -1 || mp[nx][ny])continue;
                    addd(u, v, INF);
                }
            }
            else if(((i + j) & 1) && !mp[i][j])addd(getid(i,j),T,1);
        }
    }
    printf("%d\n",cnt - Dinic(S,T));
    return 0;
}

例题C题解

最小路径覆盖，也是老套路了。

例题C代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}
    return x * f;
}

const int maxn = 5e3 + 10, maxm = 1e6 + 10, INF = 0x3f3f3f3f;
int n, m;

int head[maxn], tot = 1;
struct edge{
    int to, nexte, cap, flow;
    edge(int to = 0,int ne = 0,int ca = 0,int fl = 0):to(to),nexte(ne),cap(ca),flow(fl){}
}e[maxm];
void add(int u,int v,int cap){e[++tot] = edge(v,head[u],cap);head[u] = tot;}
void addd(int u,int v,int cap){add(u,v,cap);add(v, u, 0);}

int dep[maxn], cur[maxn];
int dfs(int u,int flow,int T){
    // printf("%lld\n",u);
    if(u == T)return flow;
    int rest = 0, tmp = 0;
    for(int i = cur[u];i && flow;i = e[i].nexte){
        cur[u] = i; int v = e[i].to;
        if(e[i].cap - e[i].flow > 0 && (dep[v] == dep[u] + 1)){
            tmp = dfs(v,min(flow,e[i].cap - e[i].flow),T);
            if(tmp == 0)dep[v] = INF;
            e[i].flow += tmp; e[i ^ 1].flow -= tmp;
            flow -= tmp;rest += tmp;
            if(!flow)return rest;
        }
    }
    return rest;
}
bool bfs(int S,int T){
    queue<int> que;
    for(int i = 1;i <= T;i++){dep[i] = INF;cur[i] = 0;}
    que.push(S);dep[S] = 1; cur[S] = head[S];
    while(!que.empty()){
        int u = que.front(); que.pop();
        for(int i = head[u];i;i = e[i].nexte){
            int v = e[i].to;
            if(e[i].cap - e[i].flow > 0 && dep[v] == INF){
                que.push(v);
                cur[v] = head[v];
                dep[v] = dep[u] + 1;
                if(v == T)return 1;
            }
        }
    }
    return 0;
}
int Dinic(int S,int T){
    int mxflow = 0;
    while(bfs(S,T)){mxflow += dfs(S,INF,T);}
    return mxflow;
}
int st[maxn];
int sx[maxn], sy[maxn];
int ex[maxn], ey[maxn];
bool ed[maxn][maxn];
void solve(){
    tot = 1;memset(head,0,sizeof(head));
    n = read();int S = n * 2 + 1, T = n * 2 + 2;
    for(int i = 1;i <= n;i++){
        int h, m;
        scanf("%d:%d%d%d%d%d",&h,&m,&sx[i],&sy[i],&ex[i],&ey[i]);
        st[i] = h * 60 + m;
    }
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            if(st[j] > st[i] + abs(ex[i] - sx[j]) + abs(ey[i] - sy[j])
                             + abs(ex[i] - sx[i]) + abs(ey[i] - sy[i]))
                ed[i][j] = 1;
            else ed[i][j] = 0;
    for(int k = 1;k <= n;k++)
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
                ed[i][j] |= (ed[i][k] & ed[k][j]);
    for(int i = 1;i <= n;i++){
        addd(S,i,1);addd(i + n,T,1);
        for(int j = 1;j <= n;j++)
            if(ed[i][j])addd(i,j + n,INF);
    }
    printf("%d\n",n - Dinic(S,T));
}
signed main(){
    int T = read();
    while(T--){solve();}
    return 0;
}

D题解

将整张图黑白染色，然后二分图匹配。
然后发现策略：如果先手走一个必须匹配点，后手就同样走一个必须匹配点，然后先手就输了。
所以先手一定先走非必需匹配点，这个点相邻的点一定是必须匹配点，否则不满足最大匹配。
然后判断非必需匹配点，具体而言，如果在你生成的一个匹配中没有被选择就一定是，否则需要判断在强制不选他的情况下能不能找到一条增广路，如果能就是非必需点。

D代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=  0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
    return x * f;
}
const int maxn = 3e4 + 10;
int n, m;
char ch[110][110];
inline int getid(int x,int y){return x * m + y - m;}
vector<int> edg[maxn];
const int dx[4] = { 1, 0, 0,-1};
const int dy[4] = { 0, 1,-1, 0};

int match[maxn];
bool vis[maxn];
bool dfs(int u){
    if(vis[u])return false;vis[u] = 1;
    for(int v : edg[u]){
        if(!match[v] || dfs(match[v])){
            match[v] = u;match[u] = v;
            return true;
        }
    }
    return false;
}
bool dfs1(int u){
    if(vis[u])return false;
    vis[u] = 1;bool res = 0;
    for(int v : edg[u]){
        if(res)return true;
        if(!match[v])return true;
        else res |= dfs1(match[v]);
    }
    return res;
}
vector<pair<int,int> > ans;
bool g[200][200];

signed main(){
    n = read();m = read();
    for(int i = 1;i <= n;i++)
        scanf("%s",ch[i] + 1);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(((i + j) & 1) && ch[i][j] == '.')
            for(int k = 0;k < 4;k++){
                int nx = i + dx[k], ny = j + dy[k];
                if(nx < 1 || nx > n || ny < 1 || ny > m)continue;
                if(ch[nx][ny] == '#')continue;
                edg[getid(i, j)].push_back(getid(nx,ny));
                edg[getid(nx,ny)].push_back(getid(i, j));
            }
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(((i + j) & 1)){
                memset(vis,0,sizeof(vis));
                dfs(getid(i,j));
            }
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(ch[i][j] == '#')continue;
            if(!match[getid(i, j)])ans.push_back(make_pair(i, j));
            else{
                memset(vis,0,sizeof(vis));
                vis[getid(i, j)] = 1;
                if(dfs1(match[getid(i, j)]))
                    ans.push_back(make_pair(i, j));
            }
        }
    }
    if(ans.size() == 0){puts("LOSE");return 0;}
    else{
        puts("WIN");
        for(auto i : ans)printf("%d %d\n",i.first,i.second);
    }
    return 0;
}
/*
10 12
.##.....##..  
....##....## 
............
###...###.#.
#..####...##
..#....####.
...##....##. 
#...##..##..
#..#........
..#..#.#..## 
*/

本栏目推荐文章
• 金牌导航-Burnside引理与Polya定理
• 金牌导航-数据结构优化DP
• 金牌导航-期望概率DP
• 金牌导航-费用流
• 金牌导航-网络流模型及应用
• 金牌导航-网络流初探
• 金牌导航-二分图匹配
• NOIP2023模拟9联测30 T4 金牌
• NOIP2023模拟9联测30 D. 金牌
• 拼多多·开店引流实操宝典：金牌系列“小白到高手”带你全方位玩转拼多多各种玩法

金牌基金会 金牌 基金 会员 数据结构 金牌 结构 数据 概率 金牌 玩法 金牌 全方位 宝典 金牌 网络 定理 金牌burnside polya 金牌 模型 网络 金牌 费用 金牌noip 2023 t4 金牌noip 2023