本文主要是介绍hdu 3395 Special Fish，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3395
题目大意：求交配后代 的最大值，注意每只鱼最多攻击别的一次和被攻击一次
题目思路：可能交配的鱼之间连边，用最大权匹配，KM算法
原题
Special Fish
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 893 Accepted Submission(s): 336
Problem Description
There is a kind of special fish in the East Lake where is closed to campus of Wuhan University. It’s hard to say which gender of those fish are, because every fish believes itself as a male, and it may attack one of some other fish who is believed to be female by it.
A fish will spawn after it has been attacked. Each fish can attack one other fish and can only be attacked once. No matter a fish is attacked or not, it can still try to attack another fish which is believed to be female by it.
There is a value we assigned to each fish and the spawns that two fish spawned also have a value which can be calculated by XOR operator through the value of its parents.
We want to know the maximum possibility of the sum of the spawns.
A fish will spawn after it has been attacked. Each fish can attack one other fish and can only be attacked once. No matter a fish is attacked or not, it can still try to attack another fish which is believed to be female by it.
There is a value we assigned to each fish and the spawns that two fish spawned also have a value which can be calculated by XOR operator through the value of its parents.
We want to know the maximum possibility of the sum of the spawns.
Input
The input consists of multiply test cases. The first line of each test case contains an integer n (0 < n <= 100), which is the number of the fish. The next line consists of n integers, indicating the value (0 < value <= 100) of each fish. The next n lines, each line contains n integers, represent a 01 matrix. The i-th fish believes the j-th fish is female if and only if the value in row i and column j if 1.
The last test case is followed by a zero, which means the end of the input.
The last test case is followed by a zero, which means the end of the input.
Output
Output the value for each test in a single line.
Sample Input
3 1 2 3 011 101 110 0
Sample Output
6
代码：
#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int maxn=105,OO=2147483647;
int w[maxn][maxn];
int lx[maxn],ly[maxn];
int linky[maxn];
bool visx[maxn],visy[maxn];
int slack[maxn];
int N;
bool find(int x)
{visx[x]=true;for(int y=0; y<N; ++y){if(visy[y])continue;int t=lx[x]+ly[y]-w[x][y];if(t==0){visy[y]=true;if(linky[y]==-1||find(linky[y])){linky[y]=x;return true;}}else{if(slack[y]>t)slack[y]=t;}}return false;
}
int KM()
{memset(linky,-1,sizeof(linky));memset(lx,-1,sizeof(lx));memset(ly,0,sizeof(ly));for(int i=0; i<N; ++i)for(int j=0; j<N; ++j)if(w[i][j]>lx[i])lx[i]=w[i][j];for(int x=0; x<N; ++x){for(int i=0; i<N; ++i)slack[i]=OO;for(;;){memset(visx,false,sizeof(visx));memset(visy,false,sizeof(visy));if(find(x))break;int d=OO;for(int i=0; i<N; ++i){if(!visy[i])if(d>slack[i])d=slack[i];}for(int i=0; i<N; ++i){if(visx[i])lx[i]-=d;}for(int i=0; i<N; ++i){if(visy[i])ly[i]+=d;elseslack[i]-=d;}}}int res=0;for(int j=0; j<N; ++j){if(linky[j]!=-1)res+=w[linky[j]][j];}return res;
}
int main()
{int vl[maxn];char ch;while(scanf("%d",&N)){if(N==0)break;memset(w,0,sizeof(w));for(int i=0;i<N;i++)scanf("%d",&vl[i]);for(int i=0;i<N;i++){for(int j=0;j<N;j++){cin>>ch;if(ch=='1'){w[i][j]=vl[i]^vl[j];}}}printf("%d\n",KM());}
}
这篇关于hdu 3395 Special Fish的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
