[kuangbin带你飞]专题十 匹配问题 二分匹配部分

刚回到家 开了二分匹配专题 手握xyl模板 奋力写写写 终于写完了一群模板题

A hdu1045

对这个图进行 行列的重写 给每个位置赋予新的行列 使不能相互打到的位置 拥有不同的行与列

然后左行右列 边是新的坐标 求最大匹配

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
char s[50][50];
int n ;
vector<int >q[50];
int a[50][50];
int b[50][50];
int m ;
bool vis[50];
int f[50];
bool fin(int u){
    for(int i=0;i<q[u].size();i++){
        int v =q[u][i];
        if(vis[v]){
            vis[v] = false;
            if(f[v] == -1 || fin(f[v])){
                f[v] = u ;
                return true;
            }
        }
    }
    return false;
}
int xyl(){
    int res = 0;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=m;i++){
        memset(vis,true,sizeof(vis));
        if(fin(i)){
            res ++ ;
        }
    }
    return res  ;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        if(n == 0)break;
        for(int i=1;i<=n;i++){
            scanf("%s",s[i] + 1);
        }
        for(int i = 0; i<= 40; i ++)q[i].clear();
        int cntx = 0;
        int cnt1 = 0;
        bool fl = false;
        for(int i=1;i<=n;i++){
            fl = false;
            for(int j=1;j<=n;j++){
                if(s[i][j] == 'X'){
                    fl = true;
                }
                else {
                    if(fl == true){
                        cntx ++ ;
                        fl = false;
                    }
                    a[i][j] = cntx + i;
                    cnt1 =a[i][j] ;
                }
            }
        }
        int cnty = 0;
        int cnt2 = 0;
        fl = false;
        for(int j=1;j<=n;j++){
            fl = false;
            for(int i=1;i<=n;i++){
                if(s[i][j] == 'X'){
                    fl = true;
                }
                else {
                    if(fl == true){
                        cnty ++ ;
                        fl = false;
                    }
                    b[i][j] = cnty + j ;
                    cnt2 = b[i][j] ;
                }
            }
        }
        for(int i = 1; i<=n ;i ++){
            for(int j = 1; j<=n; j ++) {
                if(s[i][j] != 'X'){
                    q[a[i][j]].push_back(b[i][j]);
                }
            }
        }
        m = max(cnt1,cnt2) ;
        int ans = xyl();
        printf("%d\n",ans);
    }
}

B hdu2444

double room的意思 不是两个房间 是双人间

所以题意就是判断二分图 顺便求最大匹配

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
vector<int >q[205];
int n , m ;
int co[205];
bool vis[205];
bool bfs(int u){
    queue<int>que;
    que.push(u);
    co[u] = 0;
    while(!que.empty()){
        int f = que.front();que.pop();
        for(int i = 0; i< q[f].size(); i ++){
            int v = q[f][i];
            if(co[v] == -1){
                co[v] = co[f] ^ 1 ;
                que.push(v);
            }
            else {
                if(co[v] == co[f]){
                    return false;
                }
            }
        }
    }
    return true;
}
int linker[205];
bool fin(int u){
    for(int i=0;i<q[u].size();i++){
        int v = q[u][i];
        if(vis[v]){
            vis[v] = false ;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u ;
                return true;
            }
        }
    }
    return false;
}
int xyl(){
    int res = 0;
    memset(linker , -1 , sizeof(linker));
    for(int i = 1; i<= n ; i ++ ){
        memset(vis, true , sizeof(vis));
        if(fin(i)){
            res ++ ;
        }
    }
    return res ;
}
int main(){
    // freopen("in.cpp" , "r" , stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i = 1; i<=n ;i ++)q[i].clear();
        for(int i = 1; i<=m ;i ++){
            int a,b ;
            scanf("%d%d",&a, &b);
            q[a].push_back(b);
            q[b].push_back(a);
        }
        memset(co, -1 , sizeof(co));
        bool ok = true;
        for(int i = 1; i<=n ;i ++){
            if(co[i] == -1){
                if(!bfs(i)){
                    ok = false;
                }
            }
        }
        if(ok == false){
            printf("No\n");
            continue ;
        }
        int ans = xyl() ;
        printf("%d\n",ans/2);
    }
}

C hdu1083

一边课程 一边学生 最大匹配是否等于课程

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , p ;
bool vis[305];
vector <int >q[305];
int linker[305];
bool fin(int u){
    for(int i = 0; i< q[u].size() ;i ++ ){
        int v = q[u][i];
        if(vis[v]){
            vis[v] = false;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u ;
                return true;
            }
        }
    }
    return false;
}
int xyl(){
    int res = 0 ;
    memset(linker , -1 ,sizeof(linker));
    for(int i = 1; i<= p;i ++) {
        memset(vis,true,sizeof(vis));
        if(fin(i)){
            res ++ ;
        }
    }
    return res ;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t -- ){
        scanf("%d%d",&p,&n);
        for(int i = 1; i<= p; i ++){
            q[i].clear() ;
        }
        for(int i = 1; i<= p; i ++) {
            int x ;
            scanf("%d" , &x) ;
            for(int j = 1; j<= x; j ++ ){
                int z ;
                scanf("%d", &z );
                q[i].push_back(z);
            }
        }
        int ans = xyl () ;
        if(ans == p){
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
}

D hdu1281

不可以放车的地方不影响攻击 那就不用重新写行列了

每个坐标都是一条边 求出最大匹配之后枚举每个坐标不可用 是不是重要点

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , m ;
int x ;
vector<int >q[105];
int banx,bany;
int inx[10500];
int iny[10500];
int linker[105];
bool vis[105];
bool fin(int u){
    for(int i = 0; i< q[u].size() ;i ++ ) {
        int v = q[u][i];
        if(u == banx && v == bany){
            continue;
        }
        if(vis[v]){
            vis[v] = false;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u ;
                return true;
            }
        }
    }
    return false;
}
int xyl(){
    int res = 0 ;
    memset(linker , -1 ,sizeof(linker)) ;
    for(int i = 1; i<= n ;i ++){
        memset(vis,true,sizeof(vis));
        if(fin(i)){
            res ++ ;
        }
    }
    return res ;
}
int main(){
    //freopen("in.cpp" , "r" , stdin);
    int cas = 1;
    while(scanf("%d%d%d",&n,&m,&x)!=EOF){
        for(int i = 1; i<= 100; i ++)
            q[i].clear() ;
        for(int k = 1; k <= x ;k ++) {
            int i , j ;
            scanf("%d%d",&i,&j);
            q[i].push_back(j);
            inx[k] = i ;
            iny[k] = j ;
        }
        banx = 0;
        bany = 0;
        int maxx = xyl();
        int ans = 0;
        for(int i = 1; i<= x ; i ++ ){
            banx = inx[i];
            bany = iny[i];
            int res = xyl() ;
            if(res != maxx){
                ans ++ ;
            }
        }
        printf("Board %d have %d important blanks for %d chessmen.\n",cas ++ ,ans , maxx);
    }
}

E hdu2819

这个用到了线性代数的知识

初等变换有三种 1 交换两行 2 一行*=k 3 一行 += 另一行*k

用其中的任意一种 都可以达到简化阶梯式(对角线上都是1)

并且 如果行变换可以 那么只用列变换也可以

那么 建图的方法 左边是行 右边是列 边代表左边的行 可以提供右边的列数 即有 做列数的潜力(左边的这一行经过移动 在对角线上 交点是右边的那一列)

最后linker记录的就是 经过改变后 第i行 是原来的linker[i]行

处理后输出行的变换就可以了 并且有最大匹配 = n

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
vector<int >q[105];
bool vis[105];
int linker[105];
bool fin(int u ){
    for(int i = 0; i< q[u].size(); i ++){
        int v = q[u][i];
        if(vis[v]){
            vis[v] = false;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}
int xyl(){
    int res = 0;
    memset(linker , -1 ,sizeof(linker));
    for(int i = 1; i<= n ;i ++){
        memset(vis, true, sizeof(vis));
        if(fin(i)){
            res ++ ;
        }
    }
    return res ;
}
int f[105];
int a[105];
int b[105];
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i = 1; i <= n ;i ++)q[i].clear();
        for(int i = 1; i <= n ;i ++){
            for(int j = 1; j<= n ;j ++){
                int x;
                scanf("%d", &x );
                if(x == 1)
                    q[i].push_back(j);
            }
        }
        int pd = xyl() ;
        if(pd != n){
            printf("%d\n", -1);
            continue;
        }
        for(int i = 1; i<= n ;i ++)f[i] = i ;
        int ans = 0;
        for(int i = 1; i<= n ;i ++){
            int z = linker[i];
            int where = f[z];
            if(where != i){
                ans ++ ;
                a[ans] = where ;
                b[ans] = i ;
                for(int j = 1; j<= n; j ++){
                    if(f[j] == i){
                        f[j] = where ;
                        f[z] = j ;
                    }
                }
            }
        }
        printf("%d\n",ans);
        for(int i = 1; i<= ans ;i ++){
            printf("R %d %d\n",a[i] , b[i]);
        }
    }
}

F hdu 2389

建图是容易想的 左边是人 右边是伞 最大匹配就可以了

问题在于 xyl算法的时间复杂度是VE 3000个点的情况下 稠密图会超时

在解决这类问题的时候 HK算法可以达到 E*sqrt(V)的时间复杂度

并且 在处理分层图的时候 网络流Dinic算法也可以达到E*sqrt(V)的复杂度

但是网络流也T掉了不知道为什么...

HK算法是通过每一次bfs来看 当前有没有可以进行增广的潜力 并且进行一个lv的处理

如果有潜力的话 就使用这个lv的处理 来进行增广路运算

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , m ;
int p ;
int x[3050];
int y[3050];
int s[3050];
int jl[3050];

vector<int >q[3050];
int linker[3050];
bool mx[3050];
int dx[3050] , dy[3050];
int dis ;
bool vis[3050];
int INF = 1 << 28 ;
bool bfs(){
    queue<int >que;
    dis = INF ;
    memset(dx, -1 , sizeof(dx));
    memset(dy, -1 , sizeof(dy));
    for(int i = 1; i <= n; i ++){
        if(mx[i] == false){
            que.push(i);
            dx[i] = 0;
        }
    }
    while(!que.empty()){
        int f = que.front(); que.pop ();
        if(dx[f] > dis )break;
        for(int i = 0; i < q[f].size() ;i ++ ){
            int v = q[f][i];
            if(dy[v] == -1 ){
                dy[v] = dx[f] + 1;
                if(linker[v] == -1)dis = dy[v];
                else {
                    dx[linker[v]] = dy[v] + 1 ;
                    que.push(linker[v]) ;
                }
            }
        }
    }
    if(dis == INF)return false ;
    else return true;
}
bool fin(int u ){
    for(int i = 0; i< q[u].size(); i ++ ){
        int v = q[u][i] ;
        if(vis[v] && dy[v] == dx[u] + 1){
            vis[v] = false;
            if(linker[v] != -1 && dis == dy[v])continue;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u ;
                mx[u] = true ;
                return true;
            }
        }
    }
    return false ;
}
int hk(){
    int res = 0;
    memset(mx , false , sizeof(mx)) ;
    memset(linker , -1 , sizeof(linker)) ;
    while(bfs()){
        memset(vis , true , sizeof(vis));
        for(int i = 1 ; i<= n ;i ++){
            if(mx[i] == false && fin(i)){
                res ++ ;
            }
        }
    }
    return res ;
}
bool ok[3050];
int main(){
    int t;
    scanf("%d",&t);
    int cas = 1;
    while(t -- ){
        memset(ok , false , sizeof(ok)) ;
        scanf("%d",&p);
        scanf("%d",&n);
        for(int i = 1; i<=n ;i ++)q[i].clear();
        for(int i = 1; i<=n ;i ++){
            scanf("%d%d%d",&x[i],&y[i],&s[i]);
            jl[i] = s[i] * s[i] * p * p ;
        }
        scanf("%d",&m);
        for(int i = 1; i<=m ;i ++){
            int xx , yy ;
            scanf("%d%d",&xx,&yy);
            for(int j = 1; j <= n ;j ++){
                int dis = (xx - x[j])*(xx - x[j]) + (yy - y[j])*(yy - y[j]);
                if(dis <= jl[j]){
                    q[j].push_back(i);
                    ok[j] = true;
                }
            }
        }
        int ans = hk() ;
        printf("Scenario #%d:\n",cas ++ );
        printf("%d\n\n",ans);
    }
}

G hdu4185

对于相连的两个油田连边 答案就是最大匹配

虽然点数达到了36w 边数最大也有72w左右 需要使用HK或者Dinic

但是这道题数据很小 xyl就可以过了 .. 为什么我会知道这种事情..

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
vector<int >q[360005];
int id[605][605];
char s[605][605];
int m ;
bool vis[360005];
int linker[360005];
bool fin(int u ){
    for(int i = 0 ; i< q[u].size(); i ++){
        int v = q[u][i];
        if(vis[v]){
            vis[v] = false;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u ;
                return true;
            }
        }
    }
    return false ;
}
int xyl(){
    int res = 0;
    memset(linker , -1 , sizeof(linker)) ;
    for(int i = 1 ; i<= m ;i ++){
        for(int j = 1; j<= m ;j ++)vis[j] = true;
        if(fin(i)){
            res ++ ;
        }
    }
    return res;
}
int main(){
    int t;
    scanf("%d",&t);
    int cas = 1;
    int cnt = 0;
    memset(id, 0 , sizeof(id)) ;
    while(t -- ){
        scanf("%d" ,&n );
        int minn = cnt ;
        for(int i = 1 ; i<= n ; i ++){
            scanf("%s", s[i] + 1);
        }
        for(int i = 1 ; i<= n ; i ++){
            for(int j = 1; j<= n ; j ++){
                if(s[i][j] == '#'){
                    id[i][j] = ++ cnt ;
                }
            }
        }
        m = cnt - minn ;
        for(int i = 1; i<= m ;i ++){
            q[i].clear() ;
        }
        for(int i = 1; i<= n ; i ++ ){
            for(int j = 1; j <= n ;j ++){
                if(id[i][j] > minn){
                    if(id[i+1][j] > minn){
                        int u = id[i][j] - minn ;
                        int v = id[i+1][j] - minn ;
                        q[u].push_back(v) ;
                        q[v].push_back(u) ;
                    }
                    if(id[i][j+1] > minn){
                        int u = id[i][j] - minn ;
                        int v = id[i][j+1] - minn ;
                        q[u].push_back(v) ;
                        q[v].push_back(u) ;
                    }
                }
            }
        }
        int ans = xyl();
        printf("Case %d: %d\n",cas ++ , ans/2);
    }
}

H hdu1054

求一下最小点覆盖就可以了 最小点覆盖 = 最大匹配

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
vector<int >q[50000];
int linker[50000];
bool vis[50000];
bool fin(int u){
    for(int i = 0 ; i< q[u].size() ; i ++ ){
        int v = q[u][i];
        if(vis[v]){
            vis[v] = false;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u ;
                return true ;
            }
        }
    }
    return false ;
}
int xyl(){
    int res = 0;
    memset(linker, -1 ,sizeof(linker));
    for(int i = 0; i< n ;i ++){
        memset(vis, true , sizeof(vis));
        if(fin(i))res ++ ;
    }
    return res ;
}
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i = 0; i< n ;i ++)q[i].clear() ;
        for(int i = 1 ;i<= n ; i ++){
            int u ;
            int m ;
            scanf("%d:(%d)",&u , & m);
            for(int j = 1 ; j<= m ; j ++){
                int x;
                scanf("%d",&x);
                q[u].push_back(x);
                q[x].push_back(u);
            }
        }
        int ans = xyl();
        printf("%d\n",ans/2);
    }
}

J hdu1151 & K poj2594

题目所求 一个DAG的最小不相交路径 = DAG中的顶点 - 二分图的最大匹配

将最小相交路径转化为最小不相交路径的办法 ： 如果a可以到达b 那么a到b有一条边

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n ;
int m ;
vector<int >q[50000];
bool a[150][150];
int linker[150];
bool vis[150];
bool fin(int u){
    for(int i = 0; i < q[u].size() ;i ++ ){
        int v = q[u][i];
        if(vis[v]){
            vis[v] = false ;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u ;
                return true;
            }
        }
    }
    return false ;
}
int xyl(){
    int res = 0;
    memset(linker , -1 , sizeof(linker)) ;
    for(int i = 1; i <= n ; i ++ ){
        memset(vis , true ,sizeof(vis)) ;
        if(fin(i)){
            res ++ ;
        }
    }
    return res ;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n, &m);
        for(int i = 1; i <= n ;i ++)q[i].clear();
        memset(a, false , sizeof(a));
        for(int i = 1; i <= m ; i ++ ){
            int u , v;
            scanf("%d%d",&u , &v );
            a[u][v] = true ;
        }
        for(int i = 1; i<= n ;i ++){
            for(int j = 1; j <= n; j ++){
                for(int k = 1; k <= n ;k ++){
                    if(a[i][k] == true && a[k][j] == true){
                        a[i][j] = true;
                    }
                }
            }
        }
        for(int i = 1; i<= n ;i ++) {
            for(int j = 1 ; j <= n ;j ++){
                if(a[i][j]){
                    q[i].push_back(j) ;
                }
            }
        }
        int maxx = xyl() ;
        int ans = n - maxx ;
        printf("%d\n",ans) ;
    }
}

L hdu3829

因为题目限定了一个人的hate与love的相反 那么可以将孩子分为两部分 一部分喜欢狗 一部分喜欢猫

如果矛盾是边 那么满足二分图

求这个二分图的最大独立点集就可以了

最大独立点集 ： 一个二分图中的点的集合 里面的所有的点相互之间没有边

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , m , p;
vector<int >q[505];
int linker[505];
bool vis[505];
struct node {
    char l ;
    int num1 ;
    char h ;
    int num2 ;
    int id ;
}a[505];

bool fin(int u){
    for(int i = 0; i< q[u].size() ;i ++ ){
        int v = q[u][i];
        if(vis[v]){
            vis[v] = false ;
            if(linker[v] == -1 || fin(linker[v])){
                linker[v] = u ;
                return true;
            }
        }
    }
    return false ;
}
int cntc ;
int cntd ;
int xyl(){
    int res = 0;
    memset(linker , -1 ,sizeof(linker)) ;
    for(int i = 1 ; i <= cntc ; i ++ ){
        memset(vis , true , sizeof(vis));
        if(fin(i))
            res ++ ;
    }
    return res ;
}
int main(){
    while(scanf("%d%d%d",&n,&m,&p)!=EOF){
        for(int i = 1; i<= p ; i ++)q[i].clear();
        cntc = 0;
        cntd = 0;
        for(int i = 1; i<= p ; i ++){
            char s[50];
            scanf("%s,",s);
            a[i].l = s[0] ;
            a[i].num1 = 0;
            int len = strlen(s);
            for(int j = 1 ; j < len ; j ++)a[i].num1 *= 10 , a[i].num1 += ( s[j] - '0' );
            scanf("%s,",s);
            a[i].h = s[0] ;
            a[i].num2 = 0;
            len = strlen(s);
            for(int j = 1 ; j < len ; j ++)a[i].num2 *= 10 , a[i].num2 += ( s[j] - '0' );
            if(a[i].l == 'C'){
                cntc ++ ;
                a[i].id = cntc;
            }
            else {
                cntd ++ ;
                a[i].id = cntd ;
            }
        }
        for(int i = 1; i <= p ; i ++ ){
            for(int j = 1 ; j <= p ; j ++ ){
                if((a[i].l == a[j].h && a[i].num1 == a[j].num2) || (a[i].h == a[j].l && a[i].num2 == a[j].num1)) {
                    if(a[i].l == 'C'){
                        q[a[i].id].push_back(a[j].id) ;
                    }
                    else {
                        q[a[j].id].push_back(a[i].id);
                    }
                }
            }
        }
        int ans = xyl() ;
        printf("%d\n", p - ans) ;
    }
}

经过几天的手速练习 发现二分图难在建模 代码是很套路的东西 交给队里最菜的主代码手就可以了

所以 虽然我做了很多模板题 但是 我仍然训练了我在队里的担当 ...

剩下的明天开始做吧 ...