2016-09-16

HDU 3395 Special Fish【KM or 费用流】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3395

题意：

给定$n$条鱼的价值及他们之间的攻击和被攻击关系，一个条鱼仅可以攻击和被攻击一次，攻击产生的价值为两条鱼的异或，问产生的最大结果？

分析：

比较裸的KM算法，但是可以考虑用最小费用流解决，最小费用流的前提是最大流，但是题目要求的最小费用却不一定是最大流，这时需要额外添加一下边，可以直接将左边的点向超级汇点$t$连一条边，权值为0，流量为1。
这个套路在byvoid的二分图带权匹配 KM算法与费用流模型建立也有提到过。

代码：

下面是用KM做的。。

/*************************************************************************
    > File Name: 3395.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/14 17:34:48
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
int nm, nn;
const int maxn = 1e2 + 5, INF = 0x3f3f3f3f;
int usex[maxn], usey[maxn], match[maxn], lx[maxn], ly[maxn], slack[maxn];
int z[maxn][maxn];
int a[maxn];
bool Find(int x)
{
    usex[x] = 1;
    for(int i = 0; i < nm; i++){
        if(usey[i]) continue;
        int s = lx[x] + ly[i] - z[x][i];
        if(s == 0){
            usey[i] = 1;
            if(match[i] == -1|| Find(match[i] )){
                match[i] = x;
                return true;
            }
        }else if(slack[i] > s){
            slack[i] = s;
        }
    }
    return false;
}
int KM()
{
    memset(ly, 0, sizeof(ly));
    memset(match, -1, sizeof(match));
    for(int i = 0; i <nn; i++){
        lx[i] = - INF;
        for(int j = 0; j < nm; j++){
            if(lx[i] < z[i][j])
                lx[i] = z[i][j];
        }
    }
    for(int a = 0; a < nn; a++){
        memset(slack, 0x3f, sizeof(slack));
        for(;;){
            memset(usex, 0,sizeof(usex));
            memset(usey, 0, sizeof(usey));
            if(Find(a)) break;
            int d = INF;
            for(int i = 0; i < nm; i++){
                if(!usey[i] && d > slack[i]){
                    d = slack[i];
                }
            }
            for(int i = 0; i < nn; i++){
                if(usex[i]) lx[i] -= d;
            }
            for(int i = 0; i < nm; i++){
                if(usey[i]) ly[i] += d;
                else slack[i] -= d;
            }
        }
    }
    int sum = 0;
    for(int i = 0; i < nm; i++){
        if(match[i] > -1){
            sum += z[match[i]][i];
        }
    }
    return sum;
}
char t[maxn];
int main (void)
{
	int n;
	while(~scanf("%d", &n) && n){
		for(int i = 0; i < n; i++) scanf("%d", &a[i]);
		memset(z, 0, sizeof(z));
		for(int i = 0; i < n; i++){
			scanf("%s", t);
			for(int j = 0; j < n; j++){
				if(t[j] == '1') z[i][j] = a[i] ^ a[j]; 
			}
		}
		nn = n, nm =  n;
		printf("%d\n", KM());
	}
	return 0;
}