HDU 3395 Special Fish(二分图中最优匹配:有向环覆盖)
http://acm.hdu.edu.cn/showproblem.php?pid=3395
题意:
武大荷塘有N条鱼(不分性别),每条鱼有一个价值vi.且给出一个N*N的矩阵,矩阵中(i,j)格为1表示,第i条鱼会攻击第j条鱼并产下卵.
产卵的数量= vi XOR vj. 现在每条鱼只能被攻击1次,且每条鱼只会攻击它可能会攻击的所有鱼中的一条(哪些其他鱼它会攻击已经在N*N矩阵中给出).现在要你求这N条鱼产卵数目的最大值.
分析:
如果i鱼会攻击j鱼,那么i->j有一条权值为产卵数的有向边.如果i不攻击j,那么它们有一条i->j的权值为0的有向边.其实本题就是要找权值和最大的几个不相交的有向环,它们正好完全覆盖了该有向图的所有定点.
而最优匹配又对应了每个有向环的解集合,所有就能转化为求最优匹配的权值了.
由于每次产卵活动都是由一条鱼攻击另一条鱼构成的.且任意两次攻击活动的 攻击鱼必然不同,被攻击鱼也必然不同(一条鱼只能攻击1次且被攻击1次).
所以其他这就是一条匹配边了.
建立二分图: 将N条鱼分成左右两个点集,左点集放1到N条攻击的鱼,右点集放1到N条被攻击的鱼.如果左i会攻击右j,那么就在左i与右j之间连一条权值为它们产卵数目的边.(如果不会攻击,那就连一条权值为0的边)
产卵数目最多就对应了我们求该二分图的最优匹配权值了.
结论:一个产卵数目最多的方案必与一个二分图的最优匹配一一对应.(假设有100条鱼且产卵数目最多的方案是1攻击2,2攻击3,3攻击4,其他鱼不攻击.那么匹配边就是1->2’
2->3’ 3->4’ 其他边随意取权值0的边,因为是完全图.
反之二分图的最优匹配必然也能对应出一个产卵数目的方案. )
所以如果有更优的产卵数目方案,那么它必定能对应出一个更优的二分图最优匹配,所以我们如果用KM算法不会丢失最优产卵方案.那么我们会不会用过KM算法求得一个不存在对应产卵方案的最优匹配?
不会,因为两者必然是一一对应的映射关系.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 100+5;
struct Max_Match
{
int n,W[maxn][maxn];
int Lx[maxn],Ly[maxn];
bool S[maxn],T[maxn];
int left[maxn];
bool match(int i)
{
S[i]=true;
for(int j=1;j<=n;j++)if(Lx[i]+Ly[j]==W[i][j] && !T[j])
{
T[j]=true;
if(left[j]==-1 || match(left[j]))
{
left[j]=i;
return true;
}
}
return false;
}
void update()
{
int a=1<<30;
for(int i=1;i<=n;i++)if(S[i])
for(int j=1;j<=n;j++)if(!T[j])
a=min(a, Lx[i]+Ly[j]-W[i][j]);
for(int i=1;i<=n;i++)
{
if(S[i]) Lx[i] -=a;
if(T[i]) Ly[i] +=a;
}
}
int solve(int n)
{
this->n=n;
memset(left,-1,sizeof(left));
for(int i=1;i<=n;i++)
{
Lx[i]=Ly[i]=0;
for(int j=1;j<=n;j++) Lx[i]=max(Lx[i],W[i][j]);
}
for(int i=1;i<=n;i++)
{
while(true)
{
for(int j=1;j<=n;j++) S[j]=T[j]=false;
if(match(i)) break;
else update();
}
}
int ans=0;
for(int i=1;i<=n;i++)
ans+= W[left[i]][i];
return ans;
}
}KM;
int main()
{
int n,val[maxn];
while(scanf("%d",&n)==1 && n)
{
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
char v;
scanf(" %c",&v);
if(v=='1') KM.W[i][j]= val[i]^val[j];
else KM.W[i][j]=0;
}
printf("%d\n",KM.solve(n));
}
return 0;
}
分享到:
相关推荐
本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本概念、图的遍历、图的搜索、图的匹配、图的.isConnected性、图的最短路径、图的最小生成树、图的拓扑排序等多个方面。 图论是一个重要的计算机科学领域,...
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDUACM2010版13二分匹配及其应用.ppt
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
HDU1059的代码
杭电ACMhdu1163
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)