性感代码在线求调,Dinic 80pts,TLE on #9、10
查看原帖
性感代码在线求调,Dinic 80pts,TLE on #9、10
470960
Yellow_and_Strong楼主2023/8/15 14:19
#include <bits/stdc++.h>
#define INF 0x7fffffff

using namespace std;

const int MAX = 110;

inline int read()
{
    int x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
inline void write (int x)
{
    if (x > 9) write(x / 10);
    putchar (x % 10 + 48);
}

int n, p, q, S, T;
struct Edge { int to, nxt, res_cap; }e[((MAX * MAX) << 1) + MAX * 3]; int head[MAX * 3], _head[MAX * 3], cnt = 1;
inline void add (int u, int v, int c) { e[++ cnt] = (Edge){v, head[u], c}, head[u] = cnt; }
inline void input()
{
    n = read(), p = read(), q = read();
    S = 0, T = p + n * 2 + q + 1;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= p; ++ j)
        {
            bool x = read(); int u = j, v = i + p;
            if (x) add(u, v, 1), add(v, u, 0);
        }
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= q; ++ j)
        {
            bool x = read(); int u = i + p + n, v = j + p + n * 2;
            if (x) add(u, v, 1), add(v, u, 0);
        }
}

inline void G_build()
{
    for (int i = 1; i <= p; ++ i)
        add(S, i, 1), add(i, S, 0);
    for (int i = 1; i <= q; ++ i)
        add(i + p + n * 2, T, 1), add(T, i + p + n * 2, 0);
    for (int i = 1; i <= n; ++ i)
        add(i + p, i + p + n, 1), add(i + p + n, i + p, 0);
}

int d[MAX * 3], ans;
inline bool bfs()
{
    queue <int> Q; memset(d, 0, sizeof(d));
    d[S] = 1, Q.push(S);
    while (!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (!d[v] and e[i].res_cap)
                d[v] = d[u] + 1, Q.push(v);
        }
    }
    return d[T];
}
int dfs (int u, int _flow)
{
    if (u == T or !_flow) return _flow;
    int ret = 0;
    for (int &i = _head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to, __flow;
        if (d[v] == d[u] + 1 and (__flow = dfs(v, min(_flow - ret, e[i].res_cap))))
        {
            ret += __flow, e[i].res_cap -= __flow, e[i ^ 1].res_cap += __flow;
            if (ret == _flow) return ret;
        }
    }
    return ret;
}
inline void Dinic()
{
    while (bfs())
        memcpy(_head, head, sizeof(int) * (p + n * 2 + q + 2)), ans += dfs(S, INF);
}

inline void output() { write(ans), putchar('\n'); }

int main()
{
    input();
    G_build();
    Dinic();
    output();
    return 0;
}
2023/8/15 14:19
加载中...