Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2367 Accepted Submission(s): 878
题目链接：HDU 3395
这题跟卖啤酒那差不多，一条鱼只能攻击一次也只能被攻击一次，因此把鱼拆成攻击点1~n和被攻击点n+1~2*n，然后加入源汇点连边即可，但是最大的值不一定是最大流的情况下出现的，因此要在找dis[T]大于等于0的时候停止寻找即可。这题还有一个最大的坑！负号-和异或号^的优先级不一样，记得加括号…………
代码：
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=110;
const int M=N+N+N*N;
struct edge
{
int to,nxt,cap,cost;
edge(){}
edge(int _to,int _nxt,int _cap,int _cost):to(_to),nxt(_nxt),cap(_cap),cost(_cost){}
};
edge E[M<<1];
int head[N<<1],tot;
int dis[N<<1],pre[N<<1],path[N<<1];
bitset<N<<1>vis;
char Mat[N][N];
int mc,mf,val[N];
void init()
{
CLR(head,-1);
tot=0;
mc=mf=0;
}
inline void add(int s,int t,int cap,int cost)
{
E[tot]=edge(t,head[s],cap,cost);
head[s]=tot++;
E[tot]=edge(s,head[t],0,-cost);
head[t]=tot++;
}
int SPFA(int s,int t)
{
CLR(dis,INF);
vis.reset();
queue<int>Q;
dis[s]=0;
vis[s]=1;
Q.push(s);
while (!Q.empty())
{
int u=Q.front();
Q.pop();
vis[u]=0;
for (int i=head[u]; ~i; i=E[i].nxt)
{
int v=E[i].to;
if(dis[v]>dis[u]+E[i].cost&&E[i].cap>0)
{
dis[v]=dis[u]+E[i].cost;
pre[v]=u;
path[v]=i;
if(!vis[v])
{
vis[v]=1;
Q.push(v);
}
}
}
}
return dis[t]<0;
}
void MCMF(int s,int t)
{
while (SPFA(s,t))
{
int Mf=INF;
for (int i=t; i!=s; i=pre[i])
Mf=min(Mf,E[path[i]].cap);
for (int i=t; i!=s; i=pre[i])
{
E[path[i]].cap-=Mf;
E[path[i]^1].cap+=Mf;
}
mf+=Mf;
mc+=Mf*dis[t];
}
}
int main(void)
{
int n,i,j;
while (~scanf("%d",&n)&&n)
{
init();
for (i=1; i<=n; ++i)
scanf("%d",&val[i]);
int S=0,T=n+n+1;
for (i=1; i<=n; ++i)
{
scanf("%s",Mat[i]+1);
add(S,i,1,0);//n
add(i+n,T,1,0);//n
for (j=1; j<=n; ++j)
{
if(Mat[i][j]==‘1‘)
add(i,n+j,1,-(val[i]^val[j]));//n*n
}
}
MCMF(S,T);
printf("%d\n",-mc);
}
return 0;
}
HDU 3395 Special Fish（拆点+最大费用最大流）
原文：http://www.cnblogs.com/Blackops/p/6679237.html