hdu 3395(分解点+最大費用フロー)

  wa

/*
* this code is made by LinMeiChen
* Problem: hdu 3395
* Type of Problem:    
* Thinking:
* Feeling:
*/
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<list>
using namespace std; typedef long long lld; typedef unsigned int ud;
#define oo 0x3f3f3f3f
#define maxn 1500
#define maxm 24008
struct Edge { int v, f, c, next; }E[maxm]; int tol; int head[maxn],pre[maxn]; int dis[maxn], mark[maxn]; int value[maxn], q[maxm]; int front, rear; bool Spfa(int s, int t) {
    fill(dis, dis + maxn, oo);
    memset(mark, 0, sizeof mark);
    memset(pre, -1, sizeof pre);
    front = rear = 0;
    q[rear++] = s;
    dis[s] = 0;
    mark[s] = 1; while (front<rear) { int u = q[front++];
        mark[u] = 0; for (int i = head[u]; i != -1; i = E[i].next) { int v = E[i].v; if (E[i].f>0 && dis[v] > dis[u] + E[i].c) {
                pre[v] = i;
                dis[v] = dis[u] + E[i].c; if (!mark[v]) {
                    q[rear++] = v;
                    mark[v] = 1; } } } } return dis[t] != oo; } int maxcostflow(int s, int t) { int maxcost = 0; while (Spfa(s, t)) { int minflow = oo; for (int i = pre[t]; i != -1; i = pre[E[i ^ 1].v]) {
            minflow = min(minflow, E[i].f); } for (int i = pre[t]; i != -1; i = pre[E[i ^ 1].v]) {
            E[i].f -= minflow;
            E[i ^ 1].f += minflow; }
        maxcost += dis[t]; } return maxcost; } void add_edge(int u, int v, int f, int c) {
    E[tol].v = v;
    E[tol].f = f;
    E[tol].c = c;
    E[tol].next = head[u];
    head[u] = tol++;

    E[tol].v = u;
    E[tol].f = 0;
    E[tol].c = -c;
    E[tol].next = head[v];
    head[v] = tol++; } int main() { int n; char va; while (scanf("%d", &n) && n) { int s = 2 * n + 1; int t = s + 1;
        tol = 0;
        memset(head, -1, sizeof head); for (int i = 1; i <= n; i++)
            scanf("%d", &value[i]); for (int i = 1; i <= n; i++) {
            getchar();
            add_edge(s, i, 1, 0);
            add_edge(i + n, t, 1, 0);
            add_edge(i, t, 1, 0); for (int j = 1; j <= n; j++) {
                scanf("%c", &va); if(va=='1')
                    add_edge(i, j + n, 1, -(value[i] ^ value[j])); } }
        printf("%d
", -maxcostflow(s, t)); } return 0; }