头像

滑稽_ωノ

AcWing University


访客:35714

在线 



滑稽_ωノ
22小时前

A.数字

题意:
给定两个数字 $aa, b$ 求在 $aa$ 前面加连接上一个三位数之后是 $b$ 的倍数有多少种方案



B.网格

题意:
有一个 $n \times n$ 的网格图,求从 $(0, 0)$ 走到 $(n, n)$ 的最小代价
向右或向上走的代价为 $w1$,在 $k$ 个特殊的点可以向右上走,代价为 $w2$
$n \leq 10^9, k \leq 2000$


如果 $w1 * 2 \leq w2$ 那么答案为 $w1 * n * 2$

否则最多可以使用几次 $w2$

每次使用 $w2$ 都会向右上方移动,所以当且仅当 $x_i < x_j$ $and$ $y_i < y_j$ 才可以先后使用 $i, j$ 这两个特殊点

那么就可以 $DP$ 求出最多可以使用特殊点的次数 $cnt$

最终答案为 $(n * 2 - cnt * 2) * w1 + cnt * w2$

时间复杂度 $O(k^{2})$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2020;

int n, k, w1, w2;
PII p[N];
int f[N];

int main()
{
    scanf("%d%d%d%d", &n, &k, &w1, &w2);
    int m = n << 1;
    if(w1 * 2 <= w2)  return 0 * printf("%lld\n", (LL)m * w1);

    for(int i = 0; i < k; i ++)  scanf("%d%d", &p[i].x, &p[i].y);
    sort(p, p + k);

    int cnt = 0;
    for(int i = 0; i < k; i ++)
    {
        if(p[i].x >= n or p[i].y >= n)  continue;
        f[i] = 1;
        for(int j = 0; j < i; j ++)
            if(p[j].x < p[i].x and p[j].y < p[i].y and f[j] + 1 > f[i])  f[i] = f[j] + 1;
        if(f[i] > cnt)  cnt = f[i];
    }
    m -= cnt * 2;
    printf("%lld\n", (LL)m * w1 + (LL)cnt * w2);
    return 0;
}

C.有向无环图

题意:
给定 $K$ 要求构造一个没有重边的有向无环图,使得 $1$ 到 $n$ 的方案数为 $K$
点数不得超过 $N$

测试点 $1~3$ 有 $K < N \leq 1000$
测试点 $4~5$ 有 $N = 66, K \leq 2^{64}$


当 $K < N$ 时,我们可以这样构造

1 -> n
1 -> 2 -> n
1 -> 3 -> n
1 -> 4 -> n
……

总点数为 $K + 1$


考虑一种“完全DAG”
假设共 $n$ 个点从 $1$ 到 $n$ 编号,每个点都向所有编号大于它的点连一条边
这样的图从 $1$ 号点抵达 $i > 1$ 号点的方案数就为 ${2} ^ {i - 2}$

我们知道任何数都可以拆分整 $2$ 的指数之和,那么我们在 $1$ 号点和 $n$ 号点之外构造这样一个图
并把需要的总方案数拆分成 $2$ 的指数即可

时间复杂度 $O(n)$ or ${64}^{2}$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef unsigned long long ULL;

const int N = 2020;

ULL k;
int n;

int main()
{
    scanf("%llu%d", &k, &n);
    if(k < n)
    {
        n = k + 1;
        printf("%d %d\n", n, (n - 2) * 2 + 1);
        printf("%d %d\n", 1, n);
        for(int i = 2; i < n; i ++)
            printf("%d %d\n%d %d\n", 1, i, i, n);
    }
    else
    {
        int p = -1, m = 0;
        for(int i = 63; i >= 0; i --)
        {
            if(k >> i & 1)
            {
                m ++;
                if(p == -1)  p = i;
            }
            if(~p)  m += i + 1;
        }
        int n = p + 3;
        printf("%d %d\n", n, m);

        for(int i = 0; i <= p; i ++)
            for(int j = -1; j < i; j ++)
                printf("%d %d\n", j + 2, i + 2);

        for(int i = p; i >= 0; i --)
            if(k >> i & 1)
                printf("%d %d\n", i + 2, n);
    }
    return 0;
}

D.分数

题意:
给出 $n$,初始有一个长度为 $n$ 的序列,第 $i$ 项为 $\frac{1}{i}$
每次找到 $i$ 最小的且分母不为 $1$ 的数 $\frac{p}{q}$,对序列中的所有数乘以 $q$ 并化简,直到所有数的分母都为 $1$

给出 $a, b$ 每次对序列操作的同时令 $a = a \times q + b$,输出 $a$ $mod$ $2^{32}$ 的结果
$n \leq 8 \times 10 ^ 7$

时间复杂度 $O(n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 8e7 + 10;

int primes[N / 10], cnt;
bool st[N];

void init(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])  primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; j ++)
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0)  break;
        }
    }
}

int n;
unsigned a, b;

int q[N];

int main()
{
    scanf("%d%u%u", &n, &a, &b);
    init(n);

    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        int j = p;
        while(true)
        {
            q[j] = p;
            if(j <= n / p)  j *= p;
            else  break;
        }
    }

    for(int i = 2; i <= n; i ++)
        if(q[i])  a = a * q[i] + b;
    printf("%u\n", a);
    return 0;
}

E.树数数

题意:
给定一棵 $n$ 个点的,以 $1$ 为根的树,每个点的颜色是黑色或者白色(初始为白)并且有权值
定义 $LCBA(a, b)$ 为点对 $a, b$ 的最近黑色公共祖先,然后进行 $m$ 次操作

操作$Q u$ 询问以 $u$ 为根的子树中所有点对的最近黑色公共祖先的权值和
操作$M u w$ 把点 $u$ 的权值修改为 $w$
操作$F u$ 对点 $u$ 的颜色取反

40%的数据 $n, m \leq 2000$
另外20%的数据保证树是随机生成的
对于100%的数据,$n \leq 2 \times {10}^{5}$ $m \leq 4 \times {10}^{5}$


60分做法

$O(n)$ 预处理每个点为根的子树中有多少点对的 $lca$ 是这个点,记为$times + sz - 1$

$O(n)$ 维护每个点到根节点路径上的最近黑点 $top[u]$(每次修改点颜色暴力遍历子树)

$O(n)$ 每次询问遍历子树,对于每个非叶子节点的点累加 $w[top[u]] \times (times[u] + sz[u] - 1)$

时间复杂度 $O(nm)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 200010, M = N << 1;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int n, m;
int f[N], w[N], col[N];

int sz[N];
LL times[N];

int dep[N], high;

void dfs(int u)
{
    dep[u] = dep[f[u]] + 1;
    if(dep[u] > high)  high = dep[u];

    sz[u] = 1;
    vector<int> v;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        dfs(j);

        v.push_back(sz[j]);
        sz[u] += sz[j];
    }
    for(int i = 0; i < v.size(); i ++)
        times[u] += (LL)v[i] * (sz[u] - v[i] - 1);
    times[u] /= 2;
    //printf("sz[%d] = %d   times[%d] = %d\n", u, sz[u], u, times[u]);
}

int top[N];         //  到根节点路径上最近的黑点

void dfs3(int u, int t)
{
    top[u] = t;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!col[j])  dfs3(j, t);
    }
}

LL res;
void dfs2(int u)
{
    if(sz[u] > 1)  res += (times[u] + sz[u] - 1) * w[top[u]];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs2(j);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    for(int i = 2; i <= n; i ++)
    {
        scanf("%d", &f[i]);
        add(f[i], i);
    }
    for(int i = 1; i <= n; i ++)  scanf("%d", &w[i]);

    dfs(1);
    if(high > 10000)  return 0;

    while(m --)
    {
        char op[2];
        int u, c;
        scanf("%s%d", op, &u);
        if(op[0] == 'Q')
        {
            res = 0;
            dfs2(u);
            printf("%lld\n", res);
        }
        else if(op[0] == 'M')
        {
            scanf("%d", &c);
            w[u] = c;
        }
        else
        {
            col[u] ^= 1;
            if(col[u])  top[u] = u;
            else
            {
                int j = u;
                while(j and !col[j])  j = f[j];
                top[u] = j;
            }
            dfs3(u, top[u]);
        }
    }
    return 0;
}


活动打卡代码 AcWing 2278. 企鹅游行

Dinic 拆点

#include<cstdio>
#include<cstring>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 210, M = 20410, INF = 0x3f3f3f3f;
const double eps = 1e-8;

int h[N], e[M], f[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

int n, S, T;

int q[N], d[N], hs[N];

bool bfs()
{
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;

    hs[S] = h[S];
    d[S] = 0;
    q[ ++ tt] = S;

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 and f[i])
            {
                d[j] = d[u] + 1;
                hs[j] = h[j];
                if(j == T)  return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T)  return limit;

    int flow = 0;
    for(int i = hs[u]; ~i and flow < limit; i = ne[i])
    {
        hs[u] = i;
        int j = e[i];
        if(d[j] == d[u] + 1 and f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t)  d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while(bfs())  while(flow = find(S, INF))  res += flow;
    return res;
}

PII p[N];
double D;

bool check(int i, int j)
{
    double dx = p[i].x - p[j].x, dy = p[i].y - p[j].y;
    return dx * dx + dy * dy < D * D + eps;
}

int main()
{
    int _;
    scanf("%d", &_);
    while(_ --)
    {
        memset(h, -1, sizeof h);
        idx = 0;

        scanf("%d%lf", &n, &D);
        S = 0, T = n * 2 + 1;

        int m = 0;
        for(int i = 1; i <= n; i ++)
        {
            int x, y, a, b;
            scanf("%d%d%d%d", &x, &y, &a, &b);
            p[i] = {x, y};
            add(S, i, a);
            add(i, i + n, b);
            m += a;
        }
        for(int i = 1; i <= n; i ++)
            for(int j = i + 1; j <= n; j ++)
                if(check(i, j))
                {
                    add(i + n, j, INF);
                    add(j + n, i, INF);
                }

        vector<int> res;
        for(T = 1; T <= n; T ++)
        {
            for(int i = 0; i < idx; i += 2)
            {
                f[i] += f[i ^ 1];
                f[i ^ 1] = 0;
            }
            if(dinic() >= m)  res.push_back(T - 1);
        }
        if(!res.size())  puts("-1");
        else
        {
            for(int i : res)  printf("%d ", i);
            puts("");
        }
    }
    return 0;
}



Dinic 拆点

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010, M = 251010, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

int n, S, T;
int g[N], w[N];

int hs[N], d[N], q[N];

bool bfs()
{
    memset(d, -1, sizeof d);
    d[S] = 0;
    hs[S] = h[S];
    int hh = 0, tt = -1;
    q[ ++ tt] = S;

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 and f[i])
            {
                d[j] = d[u] + 1;
                hs[j] = h[j];
                if(j == T)  return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T)  return limit;

    int flow = 0;
    for(int i = hs[u]; ~i and flow < limit; i = ne[i])
    {
        hs[u] = i;
        int j = e[i];
        if(d[j] == d[u] + 1 and f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t)  d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while(bfs())  while(flow = find(S, INF))  res += flow;
    return res;
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d", &n);
    S = 0, T = n * 2 + 1;

    int s = 0;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &w[i]);
        g[i] = 1;
        for(int j = 1; j < i; j ++)
            if(w[j] <= w[i])  g[i] = max(g[i], g[j] + 1);
        s = max(s, g[i]);

        add(i, n + i, 1);
        for(int j = 1; j < i; j ++)
            if(w[j] <= w[i] and g[j] + 1 == g[i])  add(n + j, i, 1);
        if(g[i] == 1)  add(S, i, 1);
    }
    for(int i = 1; i <= n; i ++)
        if(g[i] == s)  add(n + i, T, 1);

    printf("%d\n", s);
    if(s == 1)  return 0 * printf("%d\n%d\n", n, n);

    int res = dinic();
    printf("%d\n", res);
    for(int i = 0; i < idx; i += 2)
    {
        int a = e[i ^ 1], b = e[i];
        if(a == S and b == 1)  f[i] = INF;
        if(a == 1 and b == n + 1)  f[i] = INF;
        if(a == n and b == n + n)  f[i] = INF;
        if(a == n + n and b == T)  f[i] = INF;
    }
    printf("%d\n", res + dinic());
    return 0;
}


活动打卡代码 AcWing 2240. 餐饮

Dinic 拆点

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 1010, M = 100010, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

int n, F, D, S, T;

int hs[N], d[N], q[N];
bool bfs()
{
    memset(d, -1, sizeof d);
    d[S] = 0;
    hs[S] = h[S];
    int hh = 0, tt = 0;
    q[0] = S;

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 and f[i])
            {
                d[j] = d[u] + 1;
                hs[j] = h[j];
                if(j == T)  return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T)  return limit;

    int flow = 0;
    for(int i = hs[u]; ~i and flow < limit; i = ne[i])
    {
        hs[u] = i;
        int j = e[i];
        if(d[j] == d[u] + 1 and f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t)  d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while(bfs())  while(flow = find(S, INF))  res += flow;
    return res;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &F, &D);
    for(int i = 1; i <= n; i ++)
    {
        int x, y, a;
        scanf("%d%d", &x, &y);
        while(x --)
        {
            scanf("%d", &a);
            add(n * 2 + a, i, 1);
        }
        while(y --)
        {
            scanf("%d", &a);
            add(n + i, n * 2 + F + a, 1);
        }
    }
    S = 0, T = N - 1;
    for(int i = 1; i <= n; i ++)  add(i, i + n, 1);
    for(int i = 1; i <= F; i ++)  add(S, n * 2 + i, 1);
    for(int i = 1; i <= D; i ++)  add(n * 2 + F + i, T, 1);

    printf("%d\n", dinic());
    return 0;
}


活动打卡代码 AcWing 2187. 星际转移问题

Dinic 把不同时间的同一地点视为不同的点建图

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 40010, M = 100010, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

int n, m, k, S, T;
struct Ship{
    int h, cnt;
    vector<int> stations;
}ships[30];

int p[30];
int find(int x)
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int get(int i, int days)
{
    return (n + 2) * days + i;
}

int hs[N], q[N], d[N];

bool bfs()
{
    memset(d, -1, sizeof d);
    d[S] = 0;
    hs[S] = h[S];
    int hh = 0, tt = -1;
    q[ ++ tt] = S;

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 and f[i])
            {
                d[j] = d[u] + 1;
                hs[j] = h[j];
                if(j == T)  return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T)  return limit;

    int flow = 0;
    for(int i = hs[u]; ~i and flow < limit; i = ne[i])
    {
        hs[u] = i;
        int j = e[i];
        if(d[j] == d[u] + 1 and f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t)  d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while(bfs())  while(flow = find(S, INF))  res += flow;
    return res;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &m, &k);
    S = N - 2, T = N - 1;

    for(int i = 0; i <= n + 1; i ++)  p[i] = i;
    for(int i = 0; i < m; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        ships[i] = {a, b};

        vector<int> v;
        for(int j = 0; j < b; j ++)
        {
            int x;
            scanf("%d", &x);
            if(x == -1)  x = n + 1;
            v.push_back(x);
            if(j)
            {
                int pa = find(v[j - 1]), pb = find(v[j]);
                if(pa != pb)  p[pa] = pb;
            }
        }
        ships[i].stations = v;
    }

    if(find(0) != find(n + 1))  return 0 * printf("0");

    add(S, get(0, 0), k);
    add(get(n + 1, 0), T, INF);

    int days = 1, res = 0;
    while(true)
    {
        add(get(n + 1, days), T, INF);
        for(int i = 0; i <= n + 1; i ++)
            add(get(i, days - 1), get(i, days), INF);

        for(int i = 0; i < m; i ++)
        {
            int cnt = ships[i].cnt;
            int a = ships[i].stations[(days - 1 + cnt) % cnt], b = ships[i].stations[days % cnt];
            add(get(a, days - 1), get(b, days), ships[i].h);
        }
        res += dinic();
        if(res >= k)  break;
        days ++;
    }
    printf("%d\n", days);
    return 0;
}




Dinic

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 10010, M = 200010, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

int n, m, S, T;

int hs[N], d[N], q[N];
bool bfs()
{
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    hs[S] = h[S];
    d[S] = 0;
    q[ ++ tt] = S;
    while(hh <= tt)
    {
        int u = q[hh ++];
        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 and f[i])
            {
                d[j] = d[u] + 1;
                hs[j] = h[j];
                if(j == T)  return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T)  return limit;

    int flow = 0;
    for(int i = hs[u]; ~i and flow < limit; i = ne[i])
    {
        hs[u] = i;
        int j = e[i];
        if(d[j] == d[u] + 1 and f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t)  d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while(bfs())  while(flow = find(S, INF))  res += flow;
    return res;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d%d%d", &n, &m, &S, &T);
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", dinic());
    return 0;
}


活动打卡代码 AcWing 2237. 猪

Dinic (舔包建图)

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110, M = 40010, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}

int n, m, S, T;
int hs[N], d[N], q[N];

bool bfs()
{
    memset(d, -1, sizeof d);
    int hh = 0, tt = -1;
    d[S] = 0;
    hs[S] = h[S];
    q[ ++ tt] = S;

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 and f[i])
            {
                d[j] = d[u] + 1;
                hs[j] = h[j];
                if(j == T)  return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T)  return limit;

    int flow = 0;
    for(int i = hs[u]; ~i and flow < limit; i = ne[i])
    {
        hs[u] = i;
        int j = e[i];
        if(d[j] == d[u] + 1 and f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t)  d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while(bfs())  while(flow = find(S, INF))  res += flow;
    return res;
}

int w[1010], last[1010];

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &m, &n);
    S = 0, T = n + 1;
    for(int i = 1; i <= m; i ++)  scanf("%d", &w[i]);
    for(int i = 1; i <= n; i ++)
    {
        int cnt, b;
        scanf("%d", &cnt);
        while(cnt --)
        {
            int x;
            scanf("%d", &x);
            if(!last[x])  add(S, i, w[x]);
            else  add(last[x], i, INF);
            last[x] = i;
        }
        scanf("%d", &b);
        add(i, T, b);
    }
    printf("%d\n", dinic());
    return 0;
}


活动打卡代码 AcWing 2277. 秘密挤奶机

二分 Dinic

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 210, M = 80010, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], w[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
    e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx ++;
}


int n, m, K;
int S, T;

int hs[N], d[N], q[N];

bool bfs()
{
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    d[S] = 0;
    hs[S] = h[S];
    q[ ++ tt] = S;

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 and f[i])
            {
                d[j] = d[u] + 1;
                hs[j] = h[j];
                if(j == T)  return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T)  return limit;

    int flow = 0;
    for(int i = hs[u]; ~i and flow < limit; i = ne[i])
    {
        hs[u] = i;
        int j = e[i];
        if(d[j] == d[u] + 1 and f[i])
        {
            int t = find(j, min(f[i], limit - flow));
            if(!t)  d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while(bfs())  while(flow = find(S, INF))  res += flow;
    return res;
}

bool check(int mid)
{
    for(int i = 0; i < idx; i ++)
        f[i] = w[i] <= mid;

    return dinic() >= K;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n, &m, &K);
    S = 1, T = n;

    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    int l = 1, r = 1e6;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid))  r = mid;
        else  l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}


活动打卡代码 AcWing 367. 学校网络

有向图的强联通分量

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010, M = N << 1;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int n;

int dfn[N], low[N], tot;
int id[N], cnt;
int q[N], tt = -1;
bool st[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++ tot;
    q[++ tt] = u;
    st[u] = true;

    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if(st[j])
            low[u] = min(low[u], dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        ++ cnt;
        int y;
        do{
            y = q[tt --];
            st[y] = false;
            id[y] = cnt;
        }while(y != u);
    }
}

int din[N], dout[N];

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        int x;
        while(scanf("%d", &x), x)  add(i, x);
    }

    for(int i = 1; i <= n; i ++)
        if(!dfn[i])  tarjan(i);

    for(int i = 1; i <= n; i ++)
        for(int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if(a != b)  dout[a] ++, din[b] ++;
        }

    int x = 0, y = 0;
    for(int i = 1; i <= cnt; i ++)
    {
        if(!din[i])  x ++;
        if(!dout[i])  y ++;
    }
    printf("%d\n%d\n", x, cnt == 1 ? 0 : max(x, y));
    return 0;
}


活动打卡代码 AcWing 368. 银河

有向图的强联通分量 拓扑排序

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = N << 4;

int h[N], hs[N], e[M], w[M], ne[M], idx;
void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int n, m;

int dfn[N], low[N], tot;
int id[N], sz[N], cnt;
int q[N], tt = -1;
bool st[N];

void tarjan(int u)
{
    dfn[u] = low[u] = ++ tot;
    q[++ tt] = u;
    st[u] = true;

    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if(st[j])
            low[u] = min(low[u], dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        ++ cnt;
        int y;
        do{
            y = q[tt --];
            st[y] = false;
            id[y] = cnt;
            sz[cnt] ++;
        }while(y != u);
    }
}

int d[N], f[N];

LL topsort()
{
    LL res = 0;

    int hh = 0, tt = -1;
    for(int i = 1; i <= cnt; i ++)
        if(!d[i])  q[ ++ tt] = i, f[i] = 1;

    while(hh <= tt)
    {
        int u = q[hh ++];
        res += (LL)f[u] * sz[u];

        for(int i = hs[u]; ~i; i = ne[i])
        {
            int j = e[i];
            f[j] = max(f[j], f[u] + w[i]);
            if( -- d[j] == 0)  q[ ++ tt] = j;
        }
    }
    return res;
}

int main()
{
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    scanf("%d%d", &n, &m);
    while(m --)
    {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if(t == 1)  add(h, a, b, 0),  add(h, b, a, 0);
        else if(t == 2)  add(h, a, b, 1);
        else if(t == 3)  add(h, b, a, 0);
        else if(t == 4)  add(h, b, a, 1);
        else if(t == 5)  add(h, a, b, 0);
    }

    for(int i = 1; i <= n; i ++)
        if(!dfn[i])  tarjan(i);

    //for(int i = 1; i <= n; i ++)  printf("id[%d] = %d\n", i, id[i]);

    for(int i = 1; i <= n; i ++)
        for(int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if(a == b)
            {
                if(w[j])  return 0 * printf("-1");
            }
            else
                add(hs, a, b, w[j]),  d[b] ++;
        }

    printf("%lld\n", topsort());
    return 0;
}