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

大致题义：

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

?

大致思路：

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

?我们希望的答案是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
?