[最小费用流 || KM算法]hdoj 3395：Special Fish

大致题义：

    给出n条鱼之间相互攻击的关系以及每条鱼的能量值，每条鱼只能攻击或者被攻击最多一次（也就是被攻击之后无法攻击别人，或者攻击别人之后无法被攻击）。一次攻击行为产能为这两条鱼能量值的异或值。求总能量值最大是多少。

 

大致思路：

    用KM算法，把每条鱼拆做两个点，连别求最大匹配的思路很容易想到，代码如下。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int nMax=204;
const int mMax=1005;
const int inf=1<<29;
int map[nMax][nMax];
int lx[nMax],ly[nMax];
int mapch[nMax];
int stack[nMax];
bool sy[nMax],sx[nMax];
int n,m,e,cnt;
int find (int u){
    int v,t;
    sx[u]=1;
    for(v=1;v<=m;v++){
        if(sy[v]) continue;
        t=lx[u]+ly[v]-map[u][v];
        if(t==0){
            sy[v]=1;
            if(mapch[v]==-1||find(mapch[v])){
                mapch[v]=u;
                return 1;
            }
        }
        else if(t<stack[v]) stack[v]=t;
    }
    return 0;
}
int KM(){
    int i,j,k,d,sum=0;
    cnt=0;
    for(i=1;i<=m;i++)
        ly[i]=0;
    memset(mapch,-1,sizeof(mapch));
    for(i=1;i<=n;i++){
        lx[i]=-inf;
        for(j=1;j<=m;j++)
            if(map[i][j]>lx[i])
                lx[i]=map[i][j];
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            stack[j]=inf;
        while(1){
            for(k=1;k<=m;k++) sy[k]=0;
            for(k=1;k<=n;k++) sx[k]=0;
            if(find(i)) break;
            d=inf;
            for(k=1;k<=m;k++)
                if(!sy[k]&&stack[k]<d)
                    d=stack[k];
            for(k=1;k<=n;k++)
                if(sx[k]) lx[k]-=d;
            for(k=1;k<=m;k++)
                if(sy[k]) ly[k]+=d;
                else stack[k]-=d;
        }
    }
    for(i=1;i<=m;i++)
        if(mapch[i]!=-1&&map[mapch[i]][i]!=-inf){
            sum+=map[mapch[i]][i];
        }
    return sum;
}

char str[nMax];
int val[nMax];
int main(){
    int i,j,a;
    while(scanf("%d",&n)&&n){
        m=n;
        memset(map,0,sizeof(map));
        for(i=1;i<=n;i++)scanf("%d",&val[i]);
        for(i=1;i<=n;i++){
            scanf("%s",str+1);
            for(j=1;j<=n;j++){
                if(str[j]=='1'){
                    map[i][j]=val[i]^val[j];
                }
            }
        }
        printf("%d\n",KM());
    }
    return 0;
}

 

起初我用的是费用流，但是却wa了。连边构图时我很容易就能联想到，对每条鱼a，我们都将其拆做两点a和a‘。从原点向a连边，容量是1，费用是0。从a’向汇点连边，容量是1，费用是0。如果a攻击b则连接a->b'容量为1，费用为这两条鱼能产生的产能。求出费用流即可。但是却wa了……囧。后来看了 AekdyCoin 才明白。因为求出费用流的时候，流量必须是最大 。也就是这道题中得到最大产能的时候，图中的流量未必是最大。如下图

 我们希望的答案是9，但是费用流得到的结果是2！因为当费用是9的时候，当前网络还未达到最大流。

为了解决以上问题，对于每个a，我们可以连接一条边a->t，使得总流量等于鱼的数量。接下来求出最小费用即可。

 

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int inf=99999999;
const int nMax=3000;
const int mMax=2000000;
struct{
    int u,v, cap, cost, next, re;
}edge[mMax];
int ans,maxf;
int k,edgeHead[nMax];
int que[nMax],pre[nMax],dis[nMax];
bool vis[nMax],flag;
int K;
void addEdge(int u,int v,int ca,int co){////始点 终点 流量 花费
    edge[k].v=v;
    edge[k].cap=ca;
    edge[k].cost=co;
    edge[k].next=edgeHead[u];
    edge[k].re=k + 1;
    edgeHead[u]=k ++;
    edge[k].v=u;
    edge[k].cap=0;
    edge[k].cost=-co;
    edge[k].next=edgeHead[v];
    edge[k].re=k - 1;
    edgeHead[v]=k ++;
}

bool spfa(int s,int t,int n){      //始点，终点，总点数
    int i, head = 0, tail = 1;    //  长注释的地方就是从最小费用改到最大费用时需要变动的地方
    for(i = 0; i <= n; i ++){
        dis[i] = -inf;////////////
        vis[i] = false;
    }
    dis[s] = 0;
    que[0] = s;
    vis[s] = true;
    while(head != tail){
        int u = que[head];
        for(i = edgeHead[u]; i != 0; i = edge[i].next){
            int v = edge[i].v;
            if(edge[i].cap && dis[v] <dis[u] + edge[i].cost){////////
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if(!vis[v]){
                    vis[v] = true;
                    que[tail ++] = v;
                    if(tail == nMax) tail = 0;
                }
            }
        }
        vis[u] = false;
        head++;
        if(head ==nMax) head = 0;
    }
    if(dis[t] ==-inf) return false;///////////
    return true;
}

void end(int s,int t){
    int u, p;
    for(u = t;u!=s;u=edge[edge[p].re].v){
        p = pre[u];
        edge[p].cap-=1;
        edge[edge[p].re].cap+=1;
        ans+=edge[p].cost;
    }
    maxf+=1;   //总流量
}

int num[nMax];
char xxx[105][105];
int main(){
    int n,m,i,j,s,t,a,b,c;
    while(scanf("%d",&n)!=EOF&&n){
        k=1;
        ans=maxf=0;
        s=0,t=2*n+1;
        memset(edgeHead,0,sizeof(edgeHead));
        for(i=1;i<=n;i++){
            scanf("%d",&num[i]);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%s",xxx[i]+1);
        }
        for(i=1;i<=n;i++)
        {
            addEdge(s,i,1,0);
            addEdge(i,t,1,0);  /////!!!!!!!
            addEdge(i+n,t,1,0);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(xxx[i][j]=='1')
                {
                    a=num[i]^num[j];
                    addEdge(i,j+n,1,a);
                }
            }
        }
        while(spfa(s,t,2*n+2)){
            end(s,t);
        }
        printf("%d\n",ans);
    }
    return 0;
}

 图片转自ac大神博客 Orz