【洛谷P3973】[TJOI2015]线性代数（最小割）

题意：

给出一个\(n*n\)的矩阵\(B\)，再给出一个\(1*n\)的矩阵\(C\)。

求一个\(1*n\)的\(01\)矩阵\(A\)，使得\(D=(A\cdot B-C)\cdot A^T\)最大。

思路：

化简最后得：

\[\sum_{i=1}^n\sum_{j=1}^nB_{i,j}A_iA_j-\sum_{i=1}^nA_iC_i
\]

之后考虑所有的\(A_i\)都为\(1\)，现在要将一部分\(A_i\)变为\(0\)，最后的损失最小。

因为最后的\(A\)为\(01\)矩阵，显然最后结果为一个集合；结合损失最小，考虑最小割。

式子中只与\(A_i,A_j\)两个元素有关，单独考虑这两个元素，发现是一个很经典的最小割模型。然后解下方程就没了。

代码如下：

/*

 * Author:  heyuhhh

 * Created Time:  2019/10/29 17:17:13

 */

#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

#define all(x) (x).begin(), (x).end()

#define INF 0x3f3f3f3f

#ifdef Local

  #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

  void err() { std::cout << '\n'; }

  template<typename T, typename...Args>

  void err(T a, Args...args) { std::cout << a << ' '; err(args...); }

#else

  #define dbg(...)

#endif

void pt() {std::cout << '\n'; }

template<typename T, typename...Args>

void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

//head

const int N = 500 + 5;

int n;

int a[N][N];

template <class T>

struct Dinic{

    struct Edge{

        int v, next;

        T flow;

        Edge(){}

        Edge(int v, int next, T flow) : v(v), next(next), flow(flow) {}

    }e[N * N * 10];

    int head[N], tot;

    int dep[N];

    void init() {

        memset(head, -1, sizeof(head)); tot = 0;

    }

    void adde(int u, int v, T w, T rw = 0) {

        e[tot] = Edge(v, head[u], w);

        head[u] = tot++;

        e[tot] = Edge(u, head[v], rw);

        head[v] = tot++;

    }

    bool BFS(int _S, int _T) {

        memset(dep, 0, sizeof(dep));

        queue <int> q; q.push(_S); dep[_S] = 1;

        while(!q.empty()) {

            int u = q.front(); q.pop();

            for(int i = head[u]; ~i; i = e[i].next) {

                int v = e[i].v;

                if(!dep[v] && e[i].flow > 0) {

                    dep[v] = dep[u] + 1;

                    q.push(v);

                }

            }

        }

        return dep[_T] != 0;

    }

    T dfs(int _S, int _T, T a) {

        T flow = 0, f;

        if(_S == _T || a == 0) return a;

        for(int i = head[_S]; ~i; i = e[i].next) {

            int v = e[i].v;

            if(dep[v] != dep[_S] + 1) continue;

            f = dfs(v, _T, min(a, e[i].flow));

            if(f) {

                e[i].flow -= f;

                e[i ^ 1].flow += f;

                flow += f;

                a -= f;

                if(a == 0) break;

            }

        }

        if(!flow) dep[_S] = -1;

        return flow;

    }

    T dinic(int _S, int _T) {

        T max_flow = 0;

        while(BFS(_S, _T)) max_flow += dfs(_S, _T, INF);

        return max_flow;

    }

};

Dinic <int> solver;

int c[N], v[N];

void run() {

    solver.init();

    cin >> n;

    for(int i = 1; i <= n; i++) {

        for(int j = 1; j <= n; j++) {

            cin >> a[i][j];

        }

    }

    for(int i = 1; i <= n; i++) cin >> c[i];

    for(int i = 1; i <= n; i++) {

        for(int j = 1; j <= n; j++) v[i] += a[i][j] + a[j][i];

        v[i] -= a[i][i];

        v[i] <<= 1;

    }

    int S = 0, T = n + 1;

    for(int i = 1; i <= n; i++) {

        int t = 0;

        for(int j = 1; j <= n; j++) {

            if(i != j) {

                solver.adde(i, j, a[i][j] + a[j][i]);

                t += v[i] - a[i][j] - a[j][i];

            }

        }

        solver.adde(i, T, 2 * c[i]);

        solver.adde(S, i, t);

    }

    int ans = 0;

    for(int i = 1; i <= n; i++) {

        for(int j = 1; j <= n; j++) {

            ans += a[i][j];

        }

    }

    int flow = solver.dinic(S, T);

    dbg(ans, flow);

    cout << (ans - flow / 2) << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

    run();

	return 0;

}

巴特西

【洛谷P3973】[TJOI2015]线性代数（最小割）

最新文章

热门文章