费用流

最小费用最大流：在流量最大的前提下，总费用最小。
难点在于建图。
模板如下：

HDU 3376 Matrix Again

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int maxv = 1e+6;
const int maxe = 1e+7;
typedef int Type;
const Type INF = 0x3f3f3f3f;

struct Edge {
    int u, v;
    Type cap, flow, cost;
    Edge() {}
    Edge(int u, int v, Type cap, Type flow, Type cost) {
        this->u = u;
        this->v = v;
        this->cap = cap;
        this->flow = flow;
        this->cost = cost;
    }
};

struct MCFC {
    int n, m, s, t;
    Edge edges[maxe];
    int first[maxv];
    int next[maxe];
    int inq[maxv];
    Type d[maxv];
    int p[maxv];
    Type a[maxv];
    int Q[maxe];

    void init(int n) {
        this->n = n;
        memset(first, -1, sizeof(first));
        m = 0;
    }

    void AddEdge(int u, int v, Type cap, Type cost) {
        edges[m] = Edge(u, v, cap, 0, cost);
        next[m] = first[u];
        first[u] = m++;
        edges[m] = Edge(v, u, 0, 0, -cost);
        next[m] = first[v];
        first[v] = m++;
    }

    bool BellmanFord(int s, int t, Type &flow, Type &cost) {

        for (int i = 0; i < n; i++) d[i] = INF;
        memset(inq, false, sizeof(inq));
        d[s] = 0; inq[s] = true; p[s] = 0; a[s] = INF;
        int front, rear;
        Q[rear = front = 0] = s;
        while (front <= rear) {
            int u = Q[front++];
            inq[u] = false;
            for (int i = first[u]; i != -1; i = next[i]) {
                Edge& e = edges[i];
                if (e.cap > e.flow && d[e.v] > d[u] + e.cost) {
                    d[e.v] = d[u] + e.cost;
                    p[e.v] = i;
                    a[e.v] = min(a[u], e.cap - e.flow);
                    if (!inq[e.v]) {Q[++rear] = e.v; inq[e.v] = true;}
                }
            }
        }
        if (d[t] == INF) return false;
        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]].u;
        }
        return true;
    }

    Type Mincost(int s, int t) {
        Type flow = 0, cost = 0;
        while (BellmanFord(s, t, flow, cost));
        return cost;
    }
}H;

int mapp[610][610];

int main() {
    int n, u, v, w;
    freopen("in.txt", "r", stdin);
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &mapp[i][j]);
        int s = 0, t = 2*n*n-1;
        H.init(t+1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                H.AddEdge(i*n+j, i*n+j+n*n, 1, -mapp[i][j]);
                if (j != n-1)
                    H.AddEdge(i*n+j+n*n, i*n+j+1, 1, 0);
                if (i != n-1)
                    H.AddEdge(i*n+j+n*n, i*n+j+n, 1, 0);
            }
        }
        H.AddEdge(s, n*n, 1, 0);
        H.AddEdge(n*n-1, t, 1, 0);
        printf("%d\n", -H.Mincost(s, t));
    }
    return 0;
}

hdu 3718 Similarity

给出A， B两个分别由k不同字符组成的长度相同的字符串，现在把B中的每种字符变成A中含有的某种字符，(不能变成相同的A）,求最多能有多少个字符匹配。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

typedef int Type;
const int maxv = 1e+5;
const int maxe = 1e+7;
const int INF = 0x3f3f3f3f;

struct Edge {
    int u, v;
    Type cap, flow, cost;
    Edge() {}
    Edge(int u, int v, Type cap, Type flow, Type cost) {
        this->u = u;
        this->v = v;
        this->cap = cap;
        this->flow = flow;
        this->cost = cost;
    }
};

struct MCFC {
    int n, m, s, t;
    Edge edges[maxe];
    int first[maxv];
    int next[maxe];
    int inq[maxv];
    Type d[maxv];
    int p[maxv];
    Type a[maxv];
    int Q[maxe];

    void init(int n) {
        this->n = n;
        memset(first, -1, sizeof(first));
        m = 0;
    }

    void AddEdge(int u, int v, Type cap, Type cost) {
        edges[m] = Edge(u, v, cap, 0, cost);
        next[m] = first[u];
        first[u] = m++;
        edges[m] = Edge(v, u, 0, 0, -cost);
        next[m] = first[v];
        first[v] = m++;
    }

    bool BellmanFord(int s, int t, Type &flow, Type &cost) {

        for (int i = 0; i < n; i++) d[i] = INF;
        memset(inq, false, sizeof(inq));
        d[s] = 0; inq[s] = true; p[s] = 0; a[s] = INF;
        int front, rear;
        Q[rear = front = 0] = s;
        while (front <= rear) {
            int u = Q[front++];
            inq[u] = false;
            for (int i = first[u]; i != -1; i = next[i]) {
                Edge& e = edges[i];
                if (e.cap > e.flow && d[e.v] > d[u] + e.cost) {
                    d[e.v] = d[u] + e.cost;
                    p[e.v] = i;
                    a[e.v] = min(a[u], e.cap - e.flow);
                    if (!inq[e.v]) {Q[++rear] = e.v; inq[e.v] = true;}
                }
            }
        }
        if (d[t] == INF) return false;
        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]].u;
        }
        return true;
    }

    Type Mincost(int s, int t) {
        Type flow = 0, cost = 0;
        while (BellmanFord(s, t, flow, cost));
        return cost;
    }
}H;
char A[10000 + 10], B[5], C[10000 + 10], vis[2][52 + 10];
int mapp[26 + 10][26 + 10];

int main() {
    int tcase, n, m, k;
    //freopen("in.txt", "r", stdin);
    scanf("%d", &tcase);
    while (tcase--) {
        scanf("%d%d%d", &n, &k, &m);
        for (int i = 0; i < n; i++) {
            scanf("%s", B);
            A[i] = B[0];
        }
        while (m--) {
            int s = 52, t = s+1;
            H.init(t+1);
            memset(mapp, 0, sizeof(mapp));
            for (int i = 0; i < n; i++) {
                scanf("%s", B);
                mapp[A[i] - 'A'][B[0] - 'A']++;
                C[i] = B[0];
            }
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < 26; j++) {
                    if (mapp[i][j]) {
                        H.AddEdge(i, j+26, 1, -mapp[i][j]);
                    }
                }
            }
            memset(vis, 0, sizeof(vis));
            for (int i = 0; i < n; i++) {
                int a = A[i] - 'A', b = C[i]-'A'+26;
                if (!vis[0][a]) {
                    vis[0][a] = 1;
                    H.AddEdge(s, A[i] - 'A', 1, 0);
                }
                if (!vis[1][b]) {
                    vis[1][b] = 1;
                    H.AddEdge(C[i]-'A'+26, t, 1, 0);
                }
            }
            double len = n * 1.0;
            printf("%.4f\n", -H.Mincost(s, t)*1.0/len);
        }
    }
    return 0;
}