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