題意比較奇葩，就是n條魚，相互之間在map==1時能交配生出他們val的異或值的后代，求最大后代的值。

直接套用模板。。。。這里發(fā)現(xiàn)之前的模板有錯，所以我用這個模板重新去敲前面那題，找一下前面的錯誤。。。找模板真不是好習(xí)慣。。。

?

代碼:

#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++){//初始化頂標(biāo)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){//直到每個點都成功匹配,才結(jié)束循環(huán)memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(dfs(i))break; //如果點 i 成功匹配,則不需要調(diào)整定標(biāo)值/*------------頂標(biāo)調(diào)整------------*/int lack=INT_MAX;//頂標(biāo)調(diào)整值for(j=0;j<g;j++){if(visx[j]){for(k=0;k<g;k++){//取幅度最小的值為調(diào)整值if(!visy[k])lack=min(lx[j]+ly[k]-map[j][k],lack);}}}for(j=0;j<g;j++){//調(diào)整已經(jīng)得到匹配的點對的頂標(biāo)值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; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/amourjun/archive/2013/04/18/5134178.html

總結(jié)

以上是生活随笔為你收集整理的hdu3395纯KM的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。