B - Team Gym - 102801B ( 网络流问题)

?题目链接

先占个坑，有空写一下思路?

#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define xx first
#define yy second
#define endl "\n"
#define lowbit(x) x & (-x)
#define int long long
#define ull unsigned long long
#define pb push_back
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define LF(x) fixed << setprecision(x)
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
const double eps = 1e-8;
int n, m, M;
int s, ss, t;
int mincost, maxflow;
int a[N], b[N], c[N];
int h[N], e[N], ne[N], cap[N], cost[N], idx;
int dis[N], cur[N], vis[N];
void add(int a, int b, int c, int d)
{
    e[idx] = b, ne[idx] = h[a], cap[idx] = c, cost[idx] = d, h[a] = idx++;
    e[idx] = a, ne[idx] = h[b], cap[idx] = 0, cost[idx] = -d, h[b] = idx++;
}
int bfs(int s, int t)
{
    queue<int> q;
    for (int i = 0; i <= t; i++)
        dis[i] = inf, vis[i] = 0;
    dis[s] = 0, vis[s] = 1;
    q.push(s);
    while (q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = h[u]; ~i; i = ne[i])
        {
            int w = cap[i], cot = cost[i];
            int v = e[i];
            if (w && dis[v] > dis[u] + cot)
            {
                dis[v] = dis[u] + cot;
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return dis[t] != inf;
}

int dfs(int u, int t, int flow)
{
    if (u == t)
        return flow;
    int ret = 0;
    vis[u] = 1;
    for (int i = cur[u]; ~i && ret < flow; i = ne[i])
    {
        cur[u] = i;
        int v = e[i];
        if (!vis[v] && dis[v] == dis[u] + cost[i] && cap[i])
        {
            int tt = dfs(v, t, min(cap[i], flow - ret));
            if (tt)
            {
                ret += tt;
                cap[i] -= tt;
                cap[i ^ 1] += tt;
                mincost += tt * cost[i];
            }
        }
    }
    vis[u] = 0;
    return ret;
}
void dinic(int s, int t)
{
    int sp = s, tp = t;
    while (bfs(sp, tp))
    {
        for (int i = 0; i <= t; ++i)
            cur[i] = h[i];
        int x;
        while (x = dfs(sp, tp, inf))
            maxflow += x;
    }
}
void solve()
{
    memset(h, -1, sizeof h);
    idx = 0;
    mincost = 0;
    maxflow = 0;
    cin >> n >> m >> M;

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

    s = 4 * n + 1, ss = s + 1, t = ss + 1;

    auto cal = [](int x, int y)
    {
        return (x + y) * (x ^ y) % M;
    };

    add(ss, s, m, 0);
    for (int i = 1; i <= n; ++i)
    {

        add(s, i, 1, 0);
        add(3 * n + i, t, 1, 0);
        add(n + i, 2 * n + i, 1, 0);//点有容量就把它拆成入点与出点，入点向出点连一条边限制这个点的容量。
        for (int j = 1; j <= n; ++j)
        {

            add(j, n + i, 1, -cal(a[i], b[j]));
            add(2 * n + i, 3 * n + j, 1, -cal(a[i], c[j]));
        }
    }
    dinic(ss, t);
    cout << -mincost << endl;
}
signed main()
{
    Yshanqian;
    int T;
    T = 1;
    cin >> T;
    for (int cases = 1; cases <= T; ++cases)
    {
        // cout<<"Case #"<<cases<<": ";
        solve();
    }
    return 0;
}