应该是这个里面的第二个

实在想不到为什么会被干掉了/kk，思路跟题解第一篇是一样的，考虑每一个 $a_{1,i}$ 选 $1$ 还是 $0$ 的最小割问题。

#include <cstdio>
#include <cstring>
#include <queue>
const int N = 600, M = N * N * 2, inf = 2e9;
inline void read(int& x)
{
    x = 0; int f = 1; char ch;
    while ((ch = getchar()) < '0' || ch > '9')
        f = (ch ^ '-' ? 1 : -1);
    while (x = (x << 1) + (x << 3) + ch - '0',
    (ch = getchar()) >= '0' && ch <= '9') ;
    x *= f;
}
int min(const int& a, const int& b)
{ return a < b ? a : b; }
struct edge{ int v, next, c; }E[M << 1]; int p[N], cnt;
inline void init() { memset(p, -1, sizeof (p)); cnt = 0; }
inline void insert(int u, int v, int c)
{ E[cnt].v = v; E[cnt].c = c; E[cnt].next = p[u]; p[u] = cnt++; }
inline void addedge(int u, int v, int c)
{ insert(u, v, c); insert(v, u, 0); }
std::queue<int> q; int cur[N], n, d[N], S, T;
inline bool bfs()
{
    q.push(S); memset(d, -1, sizeof (int) * (n + 2));
    d[S] = 0; cur[S] = p[S]; int u;
    while (!q.empty())
    {
        u = q.front(); q.pop();
        for (int i = p[u], v; i + 1; i = E[i].next)
        {
            v = E[i].v; 
            if (E[i].c && d[v] == -1)
            {
                d[v] = d[u] + 1;
                cur[v] = p[v]; q.push(v);
            }
        }
    }   
    return d[T] != -1;
} 
int dfs(int u, int flow)
{
    if (u == T) return flow;
    int ans = 0;
    for (int i = cur[u], v; i + 1; i = E[i].next)
    {
        v = E[i].v;
        if (E[i].c && d[v] == d[u] + 1)
        {
            int ret = dfs(v, min(E[i].c, flow));
            E[i].c -= ret; E[i ^ 1].c += ret;
            flow -= ret; ans += ret; 
            if (flow == 0) break;
        }
    }
    if (ans == 0) d[u] = -1;
    return ans;
}
inline int dinic()
{
    int ans = 0;
    while (bfs()) ans += dfs(S, inf);
    return ans;
}
int B[N][N], C[N], sum[N], tot;
int main()
{
    init(); read(n); S = 0; T = n + 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) 
            read(B[i][j]), tot += B[i][j];
    for (int i = 1; i <= n; ++i) read(C[i]);
    for (int i = 1; i <= n ; ++i)
        for (int j = 1; j <= n; ++j)   
            sum[i] += B[i][j] + B[j][i];
    for (int i = 1; i <= n; ++i) addedge(S, i, sum[i]);
    for (int i = 1; i <= n; ++i) addedge(i, T, C[i] << 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        { 
            addedge(i, j, B[i][j] + B[j][i]); 
            addedge(j, i, B[i][j] + B[j][i]);  
        }
    printf("%d\n", tot - dinic() / 2);
    return 0;
}