hdu3395纯KM

题意比较奇葩，就是n条鱼，相互之间在map==1时能交配生出他们val的异或值的后代，求最大后代的值。

直接套用模板。。。。这里发现之前的模板有错，所以我用这个模板重新去敲前面那题，找一下前面的错误。。。找模板真不是好习惯。。。

 

代码:

#include <iostream> #include <cstdio> #include <cstring> #define INT_MAX 0x3f3f3f3f #define INT_MIN -0x3f3f3f3f #define MAX 105 #define min(a,b) a<b?a:b #define max(a,b) a>b?a:b int lx[MAX],ly[MAX],match[MAX],visx[MAX],visy[MAX],lack,g; int map[MAX][MAX]; using namespace std;int dfs(int x) {//匈牙利visx[x]=1;for(int i=0;i<g;i++){if(!visy[i] && lx[x]+ly[i]==map[x][i]){visy[i]=1;if(match[i]==-1 || dfs(match[i])){match[i]=x;return 1;}}}return 0; }int KM() {int i,j,k;for(i=0;i<g;i++){//初始化顶标lx[i]=INT_MIN; ly[i]=0;for(j=0;j<g;j++)lx[i]=max(map[i][j],lx[i]);}memset(match,-1,sizeof(match));for(i=0;i<g;i++){while(1){//直到每个点都成功匹配,才结束循环memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(dfs(i))break; //如果点 i 成功匹配,则不需要调整定标值/*------------顶标调整------------*/int lack=INT_MAX;//顶标调整值for(j=0;j<g;j++){if(visx[j]){for(k=0;k<g;k++){//取幅度最小的值为调整值if(!visy[k])lack=min(lx[j]+ly[k]-map[j][k],lack);}}}for(j=0;j<g;j++){//调整已经得到匹配的点对的顶标值if(visx[j])lx[j]-=lack;if(visy[j])ly[j]+=lack;}/*---------------------------------*/}}int sum=0;for(i=0;i<g;i++){if(match[i]!=-1)sum+=map[match[i]][i];}return sum; } int main() {int n,i,j;char ch;int value[MAX];while(cin>>n){memset(map,0,sizeof(map));if(n==0)break;for(i=0;i<n;i++)cin>>value[i];for(i=0;i<n;i++)for(j=0;j<n;j++){cin>>ch;if(ch=='1'){//cout<<value[i]<<" "<<value[j]<<endl;map[i][j]=value[i]^value[j];// cout<<map[i][j]<<endl;//cout<<" **********"<<endl;}}/* for(i=0;i<n;i++){//cout<<endl;for(j=0;j<n;j++)cout<<map[i][j]<<" ";}*/g=n;int res=KM();cout<<res<<endl;}return 0; }

 

转载于:https://www.cnblogs.com/amourjun/archive/2013/04/18/5134178.html

总结

以上是生活随笔为你收集整理的hdu3395纯KM的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。