首页 > 代码库 > [ACM] HDU 3395 Special Fish （二分图最大权匹配，KM算法）

[ACM] HDU 3395 Special Fish （二分图最大权匹配，KM算法）

2024-07-30 09:21:31   222人阅读

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
3
1 2 3
011
101
110
0
 

Sample Output
6
 

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条特殊的鱼，每个鱼都有一个价值，如果鱼i ”认为“ 鱼j 性别不同，那么就攻击它，繁殖的后代的价值为 v[i] ^ v[j]， 每条鱼只能攻击或被攻击一次，问最后繁殖的后代的最大价值为多少。

也是比较裸的二分图最大权不匹配，边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]==-1||DFS(linked[y]))
            {
                linked[y]=x;
                return true;
            }
        }
        else if(slack[y]>tmp)
            slack[y]=tmp;
    }
    return false;
}

int KM()
{
    memset(linked,-1,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]!=-1)
            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\n",KM());
    }
    return 0;
}



[ACM] HDU 3395 Special Fish （二分图最大权匹配，KM算法）


联系
我们