UVALive5874 - Social Holidaying-二分图匹配/匈牙利算法

有n个家庭,m个房间,一个房间只能两个家庭住。求最大匹配。

比较标准的二分图问题。先初始化把可能的家庭建边,然后跑一边匈牙利算法。

最后的答案是最大匹配数/2,因为建图时有重复。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map> using namespace std; const int MAXN = ;
int uN,vN;
int g[MAXN][MAXN];
int linker[MAXN];
bool used[MAXN]; int dfs(int u)
{
for(int v=;v<=vN;v++) if(g[u][v] && !used[v])
{
used[v] = true;
if(linker[v] == - || dfs(linker[v]))
{
linker[v] = u;
return true;
}
}
return false;
} int Hungarian()
{
int res = ;
memset(linker,-,sizeof linker);
for(int u=;u<=uN;u++)
{
memset(used,false,sizeof used);
if(dfs(u)) res++;
}
return res;
} int T,n,m;
int R[]; map<int,int> B; int main()
{
scanf("%d",&T);
while(T--)
{
B.clear();
memset(g,,sizeof g); scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&R[i]);
}
for(int i=;i<m;i++)
{
int tmp=;
scanf("%d",&tmp);
B[tmp] = ;
} uN = n;vN = n;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(i == j) continue;
if(B[R[i]+R[j]] == )
{
g[i][j]=g[j][i]=;
}
}
} printf("%d\n",Hungarian()/);
}
}
上一篇:IIS7配置HTTPS+默认访问https路径


下一篇:使用a标签无法跳转到指定网页的解决办法