Plug It In!（匈牙利算法）

题目链接

题意

有m个插头，n个电器，每个插座上只能插选定的几个设备，且一次只能插一个设备，你有一个接口转换器，可以使得其中一个插座一次可以插3个设备，问你同一时间最多有多少设备可以供电。

分析

首先如果没有接口转换器，很明显就是一个二分图找最大匹配的问题（二分图知识总结），那么多了一个插头转换器该如何处理？其实我们可以将插头转换器看成将任意一个插座额外复制出两个来，并且这两个插座可以连接的设备和被复制的插座相同。于是，我们可以先跑一边匈牙利算最大匹配，然后枚举每个点，将每个点复制出两个，然后在这两个点都跑一次dfs看看是否可以找到增光路，并更新答案。

代码

代码语言：javascript复制

#include <bits/stdc  .h>
#define LL long long
using namespace std;
const int maxn = 5000 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

int pei[maxn], vis[maxn], temp[maxn];
vector<int> mp[maxn];

bool dfs(int x) {//普通的匈牙利找增广路
    for(int i = 0; i < mp[x].size(); i  ) {
        int y = mp[x][i];
        if(!vis[y]) {
            vis[y] = 1;
            if(!pei[y] || dfs(pei[y])) {
                pei[y] = x;
                return true;
            }
        }
    }
    return false;
}
bool dfs1(int x) {//在复制点上找增广路，更新的是temp数组
    for(int i = 0; i < mp[x].size(); i  ) {
        int y = mp[x][i];
        if(!vis[y]) {
            vis[y] = 1;
            if(!temp[y] || dfs1(temp[y])) {
                temp[y] = x;
                return true;
            }
        }
    }
    return false;
}

int main(int argc, char const *argv[]) {
    int m, n, k;
    cin >> m >> n >> k;
    for(int i = 0; i < k; i  ) {
        int x,y;
        cin >> x >> y;
        mp[x].push_back(y m);//注意建图要这样建
        mp[y m].push_back(x);
    }
    int ans = 0;
    for(int i = 1; i <= m; i  ) {
        memset(vis,0,sizeof vis);
        if(dfs(i)) ans  ;
    }
    int end = ans;
    for(int i = 1; i <= m; i  ) {
        int res = ans;
        memcpy(temp,pei,sizeof pei);//将最初的匈牙利跑出的匹配复制给temp
        mp[4501].clear();
        mp[4502].clear();
        for(int j = 0; j < mp[i].size(); j  ) {
            mp[4501].push_back(mp[i][j]);//每次将复制的两个点放在一个不会覆盖原数据的地方
            mp[4502].push_back(mp[i][j]);
        }
        memset(vis, 0, sizeof vis);//分别在两个点上找增广路
        if(dfs1(4501)) res  ;
        memset(vis, 0, sizeof vis);
        if(dfs1(4502)) res  ;
        end = max(res,end);//更新答案
    }
    cout << end <<endl;
    return 0;
}

dfs

0 人点赞