题目链接
Special Fish HDU - 3395
题意
在东湖有一种奇怪的鱼，每个鱼都认为自己是雄性且会攻击它所认为是雌性的鱼。每个鱼被攻击后都会产卵，卵的值为父母的值的异或和。
每一个鱼能攻击其他鱼一次和被攻击一次。现给定n条鱼的值以及一个01矩阵，01矩阵的值s[i][j]为1表示第i号鱼认为第j号鱼是雌性。问怎样的攻击方式会有最大的产卵值并输出最大产卵值。
分析
将所有鱼作为左侧顶点集，将所有鱼复制一份作为右侧顶点集，边的权值为左右顶点值的异或和。如此构建一个完全二分图后，求出最大权值匹配并输出即可。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;const int maxn=110;
int w[maxn][maxn],from[maxn];
int lx[maxn],ly[maxn],visx[maxn],visy[maxn];
int nx,ny,slack[maxn];bool Find(int u)
{visx[u]=1;for(int v=0;v<ny;v++)if(!visy[v]){int tmp=lx[u]+ly[v]-w[u][v];if(tmp==0){visy[v]=1;if(from[v]==-1 || Find(from[v])){from[v]=u;return true;}}else slack[v]=min(slack[v],tmp);}return false;
}
int KM()
{for(int i=0;i<nx;i++){ly[i]=0;lx[i]=-INF;for(int j=0;j<ny;j++) lx[i]=max(lx[i],w[i][j]);}memset(from,-1,sizeof(from));for(int u=0;u<nx;u++){for(int i=0;i<ny;i++) slack[i]=INF;while(true){memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(Find(u)) break;int d=INF;for(int i=0;i<ny;i++)if(!visy[i])d=min(d,slack[i]);for(int i=0;i<nx;i++)if(visx[i])lx[i]-=d;for(int i=0;i<ny;i++){if(visy[i]) ly[i]+=d;else slack[i]-=d;}}}int ans=0;for(int i=0;i<ny;i++)if(from[i]!=-1)ans+=w[from[i]][i];return ans;
}
int n,val[maxn];
char s[maxn][maxn];
int main()
{while(scanf("%d",&n) && n){nx=ny=n;//这里不使用memset，而使用循环赋值的话会超时//memset的效率比循环赋值要快得多memset(w,0,sizeof(w));/* for(int i=0;i<n;i++)for(int j=0;j<n;i++)w[i][j]=-INF;*/for(int i=0;i<n;i++)scanf("%d",&val[i]);for(int i=0;i<n;i++)scanf("%s",s[i]);for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(s[i][j]=='1') w[i][j]=val[i]^val[j];}printf("%d\n",KM());}return 0;
}
参考博客
模板总结——二分图最大权匹配