P3846:[TJOI2007]可爱的质数题解

BSGS 算法模板题

有\(a^{x} \equiv b (mod \; p)\),求\(x\)的值。我们可以来推下这个式子,首先,这个\(x \in [0, p]\),我们可以设\(x=im-j\),其中\(m=\lceil \sqrt{p} \rceil\)。显然,\(j \in [0, m], i \in [1, m]\)。式子变成这个样子:

\[a^{im}\equiv a^j b (mod \; p)\]

然后我们只需要求出后半部分,压入 map 中,再枚举前半部分即可求出。

代码

// P3846.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll p, a, b;
ll quick_power(ll base, ll tim)
{
    ll tmp = 1;
    while (tim)
    {
        if (tim & 1)
            tmp = tmp * base % p;
        base = base * base % p;
        tim >>= 1;
    }
    return tmp;
}
map<ll, ll> hashTable;
int main()
{
    scanf("%lld%lld%lld", &p, &a, &b);
    a %= p;
    if (a == 0)
    {
        if (b == 0)
            printf("0");
        else
            printf("no solution");
        return 0;
    }
    hashTable.clear();
    ll m = ceil(sqrt(p));
    for (int j = 0, x = 1; j <= m; j++, x = x * a % p)
        hashTable[x * b % p] = j;
    ll unit = quick_power(a, m);
    for (int i = 1, x = unit; i <= m; i++, x = x * unit % p)
        if (hashTable.count(x))
        {
            printf("%lld", i * m - hashTable[x]);
            return 0;
        }
    printf("no solution");
    return 0;
}

P2891:[USACO2007OPEN]吃饭 Dining 题解

思路

一道比较裸的最大流。我们创建源点\(s=0\),让食物从源点连边到每一个牛,牛再创建副本节点(当然主节点和副本节点联通,这样保证只吃一个)连接饮料节点,在连接到汇点。求最大流即可。

代码

// P2891.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000, MAX_M = 10000, INF = 0x3f3f3f3f;
int head[MAX_N], current, n, f, d, tot, dep[MAX_N], s, t, tmp;
struct edge
{
    int to, nxt, weight;
} edges[MAX_M << 1];
void addpath(int u, int v, int w)
{
    edges[current].to = v, edges[current].nxt = head[u];
    edges[current].weight = w, head[u] = current++;
}
void add(int u, int v, int w) { addpath(u, v, w), addpath(v, u, 0); }
bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(s), dep[s] = 1;
    do
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && !dep[edges[i].to])
                dep[edges[i].to] = dep[u] + 1, q.push(edges[i].to);

    } while (!q.empty());
    return dep[t] != 0;
}
int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (dep[edges[i].to] == dep[u] + 1 && edges[i].weight > 0)
        {
            int to = edges[i].to;
            int di = dfs(to, min(flow, edges[i].weight));
            if (di > 0)
            {
                edges[i].weight -= di, edges[i ^ 1].weight += di;
                return di;
            }
        }
    return 0;
}
int dinic()
{
    int ans = 0;
    while (bfs())
        while (int di = dfs(s, INF))
            ans += di;
    return ans;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &f, &d);
    s = 0, t = n * 2 + f + d + 1;
    for (int i = 1; i <= f; i++)
        add(s, i, 1);
    for (int i = 1; i <= n; i++)
        add(i + f, i + f + n, 1);
    for (int i = 1; i <= d; i++)
        add(i + 2 * n + f, t, 1);
    for (int i = 1; i <= n; i++)
    {
        int fm, dm;
        scanf("%d%d", &fm, &dm);
        while (fm--)
            scanf("%d", &tmp), add(tmp, i + f, 1);
        while (dm--)
            scanf("%d", &tmp), add(f + i + n, tmp + 2 * n + f, 1);
    }
    printf("%d", dinic());
    return 0;
}

 

HDU3062:Party 题解

思路

一道裸的 2-SAT 模型题,可以作为模板题使用。我们来分析一下:假如第\(i\)对夫妻中的丈夫和第\(j\)对夫妻中的妻子有矛盾,那么说明第\(i\)对夫妻中的丈夫可以和第\(j\)对夫妻中的丈夫坐在一起,或是第\(i\)对夫妻中的妻子可以和第\(j\)对夫妻中的妻子坐在一起。这两种都可以对答案做贡献,所以连边。

连边之后运行 Tarjan,对联通块进行染色。如果对于任意一对夫妻在一个联通块中,那么方案不可行。因为夫妻在一个联通块意味着矛盾总会发生。

代码

// HDU-3062.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30000;
int head[MAX_N], current, n, m, tmp, st[MAX_N], cur, dfn[MAX_N], low[MAX_N], tot;
int color[MAX_N], ctot;
bool inst[MAX_N];
struct edge
{
    int to, nxt;
} edges[4000400];
void addpath(int u, int v)
{
    edges[current].to = v, edges[current].nxt = head[u];
    head[u] = current++;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++tot, inst[u] = true;
    st[++cur] = u;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (!dfn[edges[i].to])
            tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]);
        else if (inst[edges[i].to])
            low[u] = min(low[u], dfn[edges[i].to]);
    if (dfn[u] == low[u])
    {
        ctot++;
        do
        {
            inst[st[cur]] = false, color[st[cur]] = ctot;
        } while (u != st[cur--]);
    }
}
bool solve()
{
    for (int i = 0; i < 2 * n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 0; i < 2 * n; i += 2)
        if (color[i] == color[i + 1])
            return false;
    return true;
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        memset(head, -1, sizeof(head)), memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low)), memset(color, 0, sizeof(color));
        memset(st, 0, sizeof(st)), memset(inst, 0, sizeof(inst));
        for (int i = 1; i <= m; i++)
        {
            int a1, a2, c1, c2;
            scanf("%d%d%d%d", &a1, &a2, &c1, &c2);
            // reverse the relationship;
            addpath(2 * a1 + c1, 2 * a2 + 1 - c2);
            addpath(2 * a2 + c2, 2 * a1 + 1 - c1);
        }
        if (solve())
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

图论学习笔记

强连通分量

一些性质

  1. 有向图中,每一个点仅属于一个强连通分量。
  2. 强连通分量具有传递性。
  3. 极大的强连通分量指的是一个强连通分量无法继续扩大。

Tarjan 算法的一些细节

  1. 当一个节点的 DFN 和 LOW 相等时,则发现了一个强连通分量,进行弾栈。

一些例题

P2002:消息扩散题解

求割点

类似于之前的 Tarjan 算法,只要\(dfn[u]\leq low[u]\),就可以认为这个点是一个割点。理解:下游的点无法除了通过点 u 的路径到达上游 dfn 更小的点,那么这个就是割点。但是还需要考虑点\(u\)为根节点的情况,因为如果点\(u\)为根的话,那么只要子树大于二就算是一个割点,因为子树间的联通必须需要根节点作为枢纽。

模板题代码:

// P3388.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 20010, MAX_M = 100010;
int head[MAX_N], current, n, m, tmpx, tmpy, low[MAX_N], dfn[MAX_N], tot;
bool ans[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_M << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void tarjan(int u, int fa)
{
    low[u] = dfn[u] = ++tot;
    int child = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        if (!dfn[edges[i].to])
        {
            tarjan(edges[i].to, fa), low[u] = min(low[u], low[edges[i].to]);
            if (low[edges[i].to] >= dfn[u] && u != fa)
                ans[u] = true;
            if (u == fa)
                child++;
        }
        low[u] = min(low[u], dfn[edges[i].to]);
    }
    if (child >= 2 && u == fa)
        ans[u] = true;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    int cnt = 0;
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i, i);
    for (int i = 1; i <= n; i++)
        if (ans[i])
            cnt++;
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++)
        if (ans[i])
            printf("%d ", i);
    return 0;
}

双联通分量

点双连通分量

概念:在无向图中,对于点对\(u,v\),在图上删除除\(u,v\)以外的任意一个点,仍然联通,那么称这个点对为点双联通分量。

边双连通分量

概念:在无向图中,对于点对\(u,v\),在图上任意删除一条边,\(u,v\)仍连通,则称其为边双连通分量。

二分图

https://www.renfei.org/blog/bipartite-matching.html

性质

二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。

二分图最小点覆盖 = 二分图最大匹配

二分图最大点独立集 = 总点数 – 二分图最大总匹配

例题:[USACO2006NOV]Asteriod,[Usaco2005 jan]Muddy Fields

匈牙利算法

模板地址:P3386 【模板】二分图匹配

bool dfs(int u, int tm)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (dfn[to] != tm)
        {
            dfn[to] = tm;
            if ((!match[to]) || dfs(match[to], tm))
            {
                match[to] = u;
                return true;
            }
        }
    }
    return false;
}

我个人认为这个是相当精妙的一个写法,可以将“继续匹配”和“向上协商”完美的结合在一起,非常的优秀。

2-SAT

此模型可以用于求出多个条件约束下变量的解集。可以通过某些矛盾关系推出可行关系做有向边,Tarjan 染色即可。

例题:HDU3062:Party 题解

POJ3041:[USACO2006NOV]Asteriod 题解

思路

我们可以使用二分图匹配来做这个题目。我们把每一个小行星的横坐标和纵坐标映射到二分图上,找最大匹配即可。

代码

// POJ3041.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_N = 510;
int n, k, head[MAX_N], current, tmpx, tmpy, dfn[MAX_N], match[MAX_N], ans;
struct edge
{
    int to, nxt;
} edges[21000];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
bool dfs(int u, int tm)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (dfn[to] != tm)
        {
            dfn[to] = tm;
            if ((!match[to]) || dfs(match[to], tm))
            {
                match[to] = u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy);
    for (int i = 1; i <= n; i++)
        if (dfs(i, i))
            ans++;
    printf("%d", ans);
    return 0;
}