首页 > 其他分享 >金牌导航-二分图匹配

金牌导航-二分图匹配

时间：2023-12-08 20:46:57浏览次数：27  
标签：二分 tmp ch return int flow dep 导航 金牌

金牌导航-二分图匹配

例题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
.##.....##..  
....##....## 
............
###...###.#.
#..####...##
..#....####.
...##....##. 
#...##..##..
#..#........
..#..#.#..## 
*/

标签：二分,tmp,ch,return,int,flow,dep,导航,金牌
From： https://www.cnblogs.com/Call-me-Eric/p/17888985.html

相关文章

  • 二分——acwing算法基础课笔记
    个人笔记，欢迎补充、指正。此次完全以个人理解来写。整数二分 整数二分有两种，分别是找左边界和找右边界。 寻找符合要求的左边界：绿色点intbsearch_1(intl,intr){while(l<r){intmid=l+r>>1;//对应下界，最左if(check(mid))r=......
  • 二分图的匹配
    定义有点扩展域并查集的意思~如果一张无向图的\(N\)个节点\((n\geq2)\)可以分成\(A,B\)两个非空集合，其中\(A\capB=\emptyset\)，并且在同一集合内的点之间都没有边相连，那么称这张无向图为一张二分图。\(A\)、\(B\)分别称为二分图的左部和右部。性质如果两个集......
  • 小程序开发实战案例之三 | 小程序底部导航栏如何设置
    小程序中最常见的功能就是底部导航栏了，今天就来看一下怎么设置一个好看的导航栏～这里我们使用的是支付宝官方小程序IDE做示范。 官方提供的底部导航栏第一步：页面创建一般的小程序会有四个tab，我们这次也是配置四个tab的导航栏。首先，我们先创建四个页面： tab最多可......
  • Prism导航
    注册导航页面注册区域使用p:RegionManager.RegionName注册页面区域<Windowx:Class="Zhaoxi.PrismRegion.Navigation.Views.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft......
  • uniapp---wap2app去掉系统自带的导航栏
    在用uniapp进行将wap站转化为app的时候，默认打包后的文件，带有系统的导航栏，下面是去除的办法：第一步：找到sitemap.json 设置titleNView为false： 第二步：在pages加入{"webviewId":"common","matchUrls":[{"hostname":"R:.*","pa......
  • 固定导航栏
    废话不多说，先看效果再上代码一、效果图二、html内容我这里用来外部样式表导入css，当然你可以根据自己的喜好<!DOCTYPEhtml><html> <head> <metacharset="utf-8"/> <title>导航栏</title><!--导入外部样式表--> <linkrel="stylesheet"h......
  • 刷题 二分
    2023.12.6cf1902B二分一般来讲我们会在以下情况用到二分：求单调函数的零点求最小值的最大，或最大值的最小很难直接算出答案，但是很好判定答案合不合法二分答案和二分查找差不多，就是check函数内是贪心dp之类的东西当用二分控制精度时，以r-l>eps为循环条件，mid选r和l都行，一般需......
  • Note - 整体二分
    其实是做题做不动了然后也不想卷whk于是跑来写这个。正式完工估计要咕咕咕了。多组询问，对于单组询问可以二分，但是每组暴力二分又会T，而且又可以离线，修改可以根据\(mid\)分到某一边，修改对询问的贡献有结合律、交换律时，可以考虑整体二分。即定义函数\(solve(l,r,pt)\)表......
  • 界面控件DevExpress WPF导航组件，助力升级应用程序用户体验！（上）
    DevExpressWPF的SideNavigation（侧边导航）、TreeView、导航面板组件能帮助开发者在WPF项目中添加Windows样式的资源管理器栏或OutlookNavBar（导航栏），DevExpressWPFNavBar和Accordion控件包含了许多开发人员友好的功能，专门设计用于帮助用户构建极佳的应用功能。P.S：DevExpressWPF......
  • Android 9.0 app全屏通过系统属性控制手势上滑是否显示虚拟导航栏和状态栏
    1.前言在9.0的系统rom产品定制化os开发中，在系统设置app的全屏后，默认会隐藏导航栏和状态栏，页面全屏显示的时候，然后底部上滑会显示虚拟状态栏和导航栏显示几秒钟后会自动消失，由于项目开发需要要求通过api来控制全屏时上滑是否显示虚拟导航栏和状态栏，这就要从上滑事件分析看如何显......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99