以前通过KM来解的,今天用最大费用最大流写一次,结果发现WA。。次奥,这不科学。。。后来才发现有一种情况没有考虑到,即首先满足的应该是最大费用,而不是流。。。
这儿有两种解决方法:
1、一种是在加边,即把二分图左边的鱼与汇点相连,流量为1,费用为0;这样才能保证在最大费用时,流量也是最大的。传送门
2、直接做最小费用流(不是最小费用最大流),将增广的结束条件改为d[t]>=0即可。如果网络负费用圈,则需要消圈。
#include <iostream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <map> using namespace std; const int maxn = 1010; const int INF = 0x3f3f3f3f; struct Edge { int from, to, cap, flow, cost; Edge(int from, int to, int cap, int flow, int cost): from(from), to(to), cap(cap), flow(flow), cost(cost) {} }; struct MCMF { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n) { this->n = n; for(int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap, int cost) { edges.push_back(Edge (from, to, cap, 0, cost)); edges.push_back(Edge (to, from, 0, 0, -cost)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool spfa(int s, int t, int &flow, int &cost) { for(int i = 0; i <= n; i++) d[i] = INF; memset(inq, 0, sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int> Q; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if(e.cap > e.flow && d[e.to] > d[u]+e.cost) { d[e.to] = d[u]+e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap-e.flow); if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } } } } if(d[t] == INF) return 0; flow += a[t]; cost += d[t]*a[t]; int u = t; while(u != s) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return 1; } int Mincost(int s, int t, int &flow, int &cost) { while(spfa(s, t, flow, cost)); return cost; } }; void readint(int &x) { char c; while(!isdigit(c)) c = getchar(); x = 0; while(isdigit(c)) { x = x*10 + c-'0'; c = getchar(); } } void writeint(int x) { if(x > 9) writeint(x/10); putchar(x%10+'0'); } /////////////////////////////////////// MCMF solver; int n, m, s, t; int C[maxn]; char str[110][110]; int main() { for(;;) { readint(n); if(!n) break; for(int i = 1; i <= n; i++) scanf("%d", &C[i]); solver.init(2*n+10); s = 2*n+1, t = 2*n+2; for(int i = 1; i <= n; i++) scanf("%s", str[i]+1); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(str[i][j] == '1') solver.AddEdge(i, j+n, 1, -(C[i]^C[j])); } for(int i = 1; i <= n; i++) { solver.AddEdge(s, i, 1, 0); solver.AddEdge(i+n, t, 1, 0); solver.AddEdge(i, t, 1, 0); } int cost = 0, flow = 0; solver.Mincost(s, t, flow, cost); printf("%d\n", -cost); } }