[ACM] HDU 3395 Special Fish （二分圖最大權匹配，KM算法）
來源：程序員人生 發布時間：2014-11-05 08:03:52 閱讀次數：2294次
Special Fish
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.
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.
Output
Output the value for each test in a single line.
Sample Input
Sample Output
Author
momodi@whu
Source
The 5th Guangting Cup Central China
Invitational Programming Contest
Recommend
notonlysuccess | We have carefully selected several similar problems for you: 1533 1853 2448 3388 3392
解題思路：
題意為有n條特殊的魚，每一個魚都有1個價值，如果魚i ”認為“ 魚j 性別不同，那末就攻擊它，繁殖的后代的價值為 v[i] ^ v[j]， 每條魚只能攻擊或被攻擊1次，問最后繁殖的后代的最大價值為多少。
也是比較裸的2分圖最大權不匹配，邊i,j的權值等于 v[i] ^ v[j] 。
http://blog.csdn.net/sr_19930829/article/details/40650359
代碼：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn=102;
const int inf=0x3f3f3f;
int nx,ny;//左右兩邊的點數
int v[maxn];//每條魚的value
int g[maxn][maxn];//鄰接矩陣
int linked[maxn];//右側的點和左側哪一個點連接
int lx[maxn],ly[maxn];//左右點的標號
int slack[maxn];//slack[j]表示右側的點j的所有不在導出子圖的邊對應的lx[i]+ly[j]-w[i][j]的最小值
bool visx[maxn],visy[maxn];
bool DFS(int x)//hungary求增廣路
{
visx[x]=true;
for(int y=0;y<ny;y++)
{
if(visy[y])
continue;
int tmp=lx[x]+ly[y]-g[x][y];
if(tmp==0)
{
visy[y]=true;
if(linked[y]==⑴||DFS(linked[y]))
{
linked[y]=x;
return true;
}
}
else if(slack[y]>tmp)
slack[y]=tmp;
}
return false;
}
int KM()
{
memset(linked,⑴,sizeof(linked));
memset(ly,0,sizeof(ly));
for(int i=0;i<nx;i++)
{
lx[i]=-inf;
for(int j=0;j<ny;j++)
if(g[i][j]>lx[i])
lx[i]=g[i][j];
}
for(int x=0;x<nx;x++)
{
for(int y=0;y<ny;y++)
slack[y]=inf;
while(true)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(DFS(x))
break;
int d=inf;
for(int y=0;y<ny;y++)
if(!visy[y]&&d>slack[y])
d=slack[y];
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 y=0;y<ny;y++)
{
if(linked[y]!=⑴)
ans+=g[linked[y]][y];
}
return ans;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n)
{
nx=ny=n;
for(int i=0;i<n;i++)
scanf("%d",&v[i]);
int ch;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%1d",&ch);//輸入格式1d
if(ch==1)
g[i][j]=v[i]^v[j];
else
g[i][j]=0;
}
}
printf("%d
",KM());
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
