题解：P13793 [SWERC 2023] Supporting everyone

· · 题解

前置芝士：

二分图最大匹配

题目大意：

有 n 个要支持国家，有两种方式支持一个国家：画国旗或带这个国家的徽章，每个国旗有 k 种颜色，每个蜡笔或徽章的价格都为 1。求最少花费多少价格，支持所有国家。

思路：

我们可以把国家放在左半边，把笔放在右半边，将每个国旗需要的颜色与对应的蜡笔连边，进行匹配即可。

问：这个思路为何正确？

答：当你的国家中所需的蜡笔都被其他国家和自己匹配完了，这边我们可以视作他去买蜡笔。如果没有匹配完，我们可以视作他是去买徽章，如果这个国家没有与蜡笔匹配，我们视作他的蜡笔都被买了，可以蹭别的国家的蜡笔。

代码（匈牙利）：

#include<bits/stdc++.h>
using namespace std;
int n,m,e;
int match[10005];
vector<int> g[5005];
bool vis[10005];
bool dfs_xyl(int x){
    for(auto i:g[x]){
        if(vis[i]){
            continue;
        }
        vis[i]=true;
        if(match[i]==0 || dfs_xyl(match[i])){
            match[i]=x;
            return true;
        }
    }
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        for(int j=1;j<=k;j++){
            int x;
            cin>>x;
            g[i].push_back(x);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(dfs_xyl(i)){
            ans++;
        }
        memset(vis,0,sizeof(vis));
    }
    cout<<ans;
    return 0;
}