先放一道二分图最大匹配:
初看这道题,嗯???和二分图有毛关系???
是的,我当初也是这么想的,如果不是有人推荐我写二分图的题,说让我写这个,我压根想不到二分图....
我们可一模拟一下这个题目来理解为什么用二分图的知识....
我们选了一个属性值1的装备,之后选2,发现只有装备1有,我们是不是要尝试给属性值为1换一个装备...
想起来了没,这不就是我们寻找最大匹配的过程吗?根据这个过程,我们可以很自然的想到将属性与装备建边...
但是显然这个题没有任何匹配的含义,为什么可以用二分图来做呢?
根据过程来启发思考就不说了,我们必须发现一些性质才能让我们理解的更深刻...
发现每个装备只能选一个属性,这就是唯一性,也就是最大匹配中每个点只能连一条边...
换句话说一个属性只能匹配一个装备(反之也可),这就是一个重要的性质,唯一性...
关于唯一性也可以有其他的应用,最普通的就是匹配问题,一一匹配,或者代表之类的...
这也是我们可以想到二分图的依据,因为这个题目中,装备具备唯一性,类似的只能选一个东西的一个属性代表一个物品,这就出现唯一性了,我们就可以考虑二分图的一些算法了...
当然模拟过程也是不错的思考的方法...
今天模考,又有暴力分可以用KM算法写,忍无可忍的我决定学习KM...
先附上一篇好的链接:好的博客!(我就是看了这个才懂得,真的棒.)
这里先贴个模板吧...
bool find(int x) { usex[x]=id;//标记使用过. for(int i=1;i<=m;++i) { if(usey[i]!=id&&cx[x]+cy[i]==w[x][i]) //如果i没使用过且在原图中 { usey[i]=id; if(!line[i]||find(line[i])) {line[i]=x;return 1;} //匈牙利算法,另找边. } } return 0; } int KM() { for(int i=1;i<=n;++i) { while(1) { int d=qwq;//赋初值为正无穷. id++;if(find(i)) break; //知道找到才推出. for(int j=1;j<=n;++j)//找出使用过的j if(usex[j]==id) for(int k=1;k<=m;++k)//找出没用过的k if(usey[k]!=id) d=min(d,cx[j]+cy[k]-w[j][k]);//寻找最小的d if(d==qwq) return -1; for(int j=1;j<=n;++j) if(usex[j]==id) cx[j]-=d;//更新标杆. for(int j=1;j<=m;++j) if(usey[j]==id) cy[j]+=d; } } int ans=0; for(int i=1;i<=m;++i) ans+=w[line[i]][i]; return ans; }
再来一波模板:
主要是初始化时注意男女顺序即可...
#include<bits/stdc++.h>
#define _ 0 using namespace std; const int N=25,qwq=1e9; int a[N][N],b[N][N],n,id; int w[N][N],usex[N],usey[N],line[N],cx[N],cy[N]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline bool find(int x) { usex[x]=id; for(register int i=1;i<=n;++i) { if(usey[i]!=id&&cx[x]+cy[i]==w[x][i]) { usey[i]=id; if(!line[i]||find(line[i])) {line[i]=x;return 1;} } } return 0; } inline int KM() { for(register int i=1;i<=n;++i) { while(1) { int d=qwq; id++; if(find(i)) break; for(register int j=1;j<=n;++j) if(usex[j]==id) for(register int k=1;k<=n;++k) if(usey[k]!=id) d=min(d,cx[j]+cy[k]-w[j][k]); if(d==qwq) return -1; for(register int j=1;j<=n;++j) if(usex[j]==id) cx[j]-=d; for(register int j=1;j<=n;++j) if(usey[j]==id) cy[j]+=d; } } int ans=0; for(register int i=1;i<=n;++i) ans+=w[line[i]][i]; return ans; } int main() { freopen("1.in","r",stdin); n=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[i][j]=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) b[i][j]=read(); for(int i=1;i<=n;++i) { int s=0; for(int j=1;j<=n;++j) { w[i][j]=a[i][j]*b[j][i]; s=max(s,w[i][j]); } cx[i]=s; } printf("%d",KM()); return (0^_^0); }