[最小费用流 || 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
?
