Login
Register
Problem list
Online status
SoulPowering...
:
2026-04-22 23:01:47
匈牙利算法准则:待字闺中,据为己有;名花有主,求他放手。!!!!!!!!!!!!!! #include
#include
using namespace std; const int N=60,M=1010; int n1,n2; int h[N],e[M],ne[M],idx; //h[1~n1]; //e[地址]:编号 bool st[N];//st[1~n2] //对于每个左点集的男生,这一轮中是否已经考虑过右边编号为i的女生,保证不重复访问造成find(i)死循环 int match[N];//match[1~n2]=1~n1; void add(int u,int v) { e[idx]=v,ne[idx]=h[u],h[u]=idx++; } bool find(int x) { //如果x号男生匹配成功,返回true,反之返回false, //一一考虑该男生的心动对象, //如果单身(match==0),直接抢走, //如果match!=0,但现男友还有其他备胎,便喧宾夺主 for(int i=h[x];i!=-1;i=ne[i]) { int j=e[i]; if(!st[j]) { st[j]=true;//不管成功与否,我都已经考虑过这个女生了 if(match[j]==0||find(match[j])) { match[j]=x; return true; } } } return false; } int main() { int T; cin>>T; while(T--) { int res=0; //初始化h[]数组全为-1,表示i号男生还没有任何心动关系 memset(h,-1,sizeof h); memset(match,0,sizeof match);//match别忘了清空,初始化为0 idx=0; cin>>n1>>n2; for(int i=1;i<=n1;i++) { int k; cin>>k; while(k--) { int m; cin>>m;//勿忘读进女生编号 add(i,m); } } for(int i=1;i<=n1;i++) { memset(st,false,sizeof st);//对于每个男生来说都还没有考虑过右边的所有女生 if(find(i))res++; } cout<
harkerhand
:
2025-04-25 17:01:18
经典板子 #include
using namespace std; #define int long long int n, m; // n: 男嘉宾数, m: 女嘉宾数 vector
> adj; // 邻接矩阵,记录每个男嘉宾喜欢哪些女嘉宾 vector
match; // match[i]表示第i个女嘉宾的匹配男嘉宾 vector
visited; // 记录在DFS过程中,某个女嘉宾是否已被访问过 // 尝试为男嘉宾u找到一个匹配 bool dfs(int u) { for (int v : adj[u]) { // 遍历男嘉宾u喜欢的所有女嘉宾v if (!visited[v]) { // 如果v没有被访问过 visited[v] = true; if (match[v] == -1 || dfs(match[v])) { // 如果女嘉宾v没有匹配,或者当前匹配可以找到新的匹配 match[v] = u; // v和u匹配 return true; } } } return false; } signed main() { int t; cin >> t; while (t--) { cin >> n >> m; adj.clear(); adj.resize(n); match.clear(); match.resize(m, -1); // 输入男嘉宾的偏好 for (int i = 0; i < n; i++) { int k; cin >> k; adj[i].resize(k); for (int j = 0; j < k; j++) { int x; cin >> x; adj[i][j] = x - 1; // 女嘉宾编号转换为0-based } } int total_match = 0; // 对每个男嘉宾尝试进行匹配 for (int i = 0; i < n; i++) { visited.clear(); visited.resize(m, false); if (dfs(i)) { total_match++; } } cout << total_match << endl; } return 0; }
Post Your Comment