前言

NOIP中有很多可以也是应该背会的模版，从数论，图论等等方面皆有很强的兼容性
先做一个简单的总结。其中的写法是我在写程序的过程中的写法。

小序

注重拆分程序，分解问题。
如下程序中:

  • void init()表示程序初始化
  • void getdata()表示程序读入数据
  • void putdata()表示程序输出数据
  • void work()表示程序主要运行逻辑

结构与存取

图的边

struct Side
{
    int _node;
    int node_;
    int next;
    int value;
};

图的节点

struct Node
{
    vector<Side> sides; //有权图时使用
    vector<int> sides;  //无权图时使用
    bool visited;
    int father;
    int dis;
};

struct重载运算符

struct Node
{
    int weight;
    bool operator<(const Node n)
    const{
        return this->weight < n.weight;
    }
};

sort()中的cmp

bool cmp(Node a,Node b)
{
    return a.weight < b.weight;
}

图的读取

vector<Node> nodes;
void getdata()
{
    Node a;
    nodes = vector<Node>(n_node + 1, a);
    int _node, node_;
    for (int i = 0; i < n_node; i++)
    {
        Side s;
        cin >> _node >> node_ >> s.value;
        s.next = node_;
        nodes[_node].sides.push_back(s);
        //若是无向图存两次
        s.next = _node;
        nodes[node_].sides.push_back(s);
    }
}

正文

GCD 欧几里得

用于求解gcd(a,b)gcd(a,b)和类似于ax+by=gcd(a,b)ax+by=gcd(a,b)等的方程(扩欧)

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b,a%b);
}

void exgcd(int a,int b,int &gcd,int &x,int &y)
{
    if(b == 0)
    {
        gcd = a;
        x = 1;
        y = 0;
        return;
    }
    gcd(b,a%b,gcd,x,y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return;
}

Fast Power 快速幂

用于求解aba^b以及ab%ka^b\%k

int qpow(int base_, int pow)
{
    if(pow == 0)
        return 1;
    int ans = 1;
    int base = base_;
    while (pow != 0)
    {
        if (pow % 2 == 1)
            ans *= base;
        base *= base;
        pow /= 2;
    }
    return ans;
}

int qpow_mod(int base_, int pow,int mod)
{
    if(pow == 0)
        return 1;
    int ans = 1;
    int base = base_ % mod;
    while (pow != 0)
    {
        if (pow % 2 == 1)
            ans = ans * base % mod;
        base = base * base % mod;
        pow /= 2;
    }
    return ans;
}

Union Find 并查集

用于解决集合的合并与查询问题，扩展后可以解决一些树和图的问题

int n_node;
vector<int> father;
vector<int> set_num; //集合元素
void init()
{
    father.clear();
    set_num = vector<int>(n_node + 1,1);
    for(int i = 0; i <= n_node; i++)
        father.push_back(i);
}
int find(int x)
{
    return father[x] == x ? x : father[x] = find(father[x]);
}
void merge(int a,int b)
{
    a = find(a);
    b = find(b);
    if(a == b)
        return;
    father[a] = b;
    set_num[b] += set_num[a]; //集合元素
    return;
}

PS:并查集可以用于储存该集合的一些属性

  • 用于存储集合元素
set_num[b] += set_num[a];
  • 用于存储集合边权之和
cur_weight = weight[find(s.node_)] + weight[find(s._node)] + s.weight;
merge(node_,_node);
weight[find(node_)] = cur_weight;

Minimum Spanning Tree 最小生成树

图论中的最小(最大)生成树问题的解决模版

include UnionFind
include Side
include operator
include read_graph

priority_queue<Side> s_queue; //value排序
void MST()
{
    while (!s_queue.empty() && max_count < n_node)
    {
        Side s = s_queue.top();
        s_queue.pop();
        if (merge(s._node, s.node_))    //表示是否不在同一集合且合并成功
            max_weight += s.value;
    }
}

Depth First Search 深度优先搜索

include Side
include Node
include read_graph

void dfs(int now)
{
    nodes[now].visited = true;
    for(int i = 0; i < nodes[now].sides.size(); i++)
    {
        int next = nodes[now].sides[i].next;
        if(!nodes[next].visited)
            dfs(next);
    }
}

Breadth First Search 宽度优先搜索

include Side
include Node
include read_graph

void bfs()
{
    queue<int> n_queue;
    n_queue.push(source);
    while(!n_queue.empty())
    {
        int now = n_queue.top();
        n_queue.pop();
        nodes[now].visited = true;
        for(int i = 0; i < nodes[now].sides.size(); i++)
        {
            int next = nodes[now].sides[i].next;
            if(!nodes[next].visited)
                n_queue.push(next);
        }
    }
}

Lowest Common Ancestor 最近公共祖先

include UnionFind
include Side 无权
include Node

struct Node
{
    vector<int> sides;
    vector<int> query;
    map<int, bool> queryed;
    map<int, int> query_result;
};

include read_graph

最近公共祖先(TarjanTarjan算法)
利用面对对象空间换时间,该算法时间复杂度O(n)O(n)
PS:其他的程序和我的查询不同，时间复杂度是O(n+q)O(n+q)

Tarjan算法的基本思路：

  1. 任选一个点为根节点，从根节点开始。
  2. 遍历该点nownow所有子节点nextnext，并标记这些子节点nextnext已被访问过。
  3. 若是nextnext还有子节点，返回第22步，否则下一步。
  4. 合并nextnext到nownow上。
  5. 寻找与当前点nownow有询问关系的点queryquery。
  6. 若是queryquery已经被访问过了，则可以确认nownow和queryquery的最近公共祖先为queryquery被合并到的父亲节点find(query)find(query)。
int n_node, n_ask, root;            //节点数,询问数,根
vector<int> father;                 //并查集father
vector<bool> vis;                   //节点访问数组
queue<pair<int, int>> query_queue;  //查询数组

struct Node
{
    vector<int> sides;              //该点邻接边
    vector<int> query;              //该点查询
    map<int, bool> queryed;         //已经查询过
    map<int, int> query_result;     //查询数据保存
};

vector<Node> nodes;

void init()
{
    cin >> n_node >> n_ask >> root;

    //并查集初始化
    father.clear();
    for (int i = 0; i <= n_node; i++)
        father.push_back(i);

    vis = vector<bool>(n_node + 1, false);

    Node a;
    nodes = vector<Node>(n_node + 1, a);

    int _node, node_;

    //读取边
    for (int i = 0; i < n_node - 1; i++)
    {
        cin >> _node >> node_;
        nodes[_node].sides.push_back(node_);
        nodes[node_].sides.push_back(_node);
    }

    //读取查询
    for (int i = 0; i < n_ask; i++)
    {
        cin >> _node >> node_;
        nodes[_node].query.push_back(node_);
        nodes[node_].query.push_back(_node);        //双向添加
        nodes[_node].queryed[node_] = false;
        nodes[node_].queryed[_node] = false;        //初始化没有查询
        query_queue.push(make_pair(_node, node_));  //添加到FIFO队列用于输出
    }
}

int find(int x)
{
    return father[x] == x ? x : father[x] = find(father[x]);
}

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y)
        return;
    father[x] = y;
    return;
}

void Tarjan(int now, int father)
{
    for (unsigned int i = 0; i < nodes[now].sides.size(); i++)
    //取出当前点的每一条边
    {
        int next = nodes[now].sides[i];
        if (next != father)
        //如果不是来的点
        {
            Tarjan(next, now);      //递归(dfs)
            merge(next, now);       //合并儿子到自己(顺序不可变)
            vis[next] = true;       //儿子已经访问过
        }
    }

    for (unsigned int i = 0; i < nodes[now].query.size(); i++)
    //取出当前点的每一个查询
    {
        int now_query = nodes[now].query[i];
        if (vis[now_query] && !nodes[now].queryed[now_query])
        //如果查询的点已经被访问过 并且 没有被对方反向查询过(防止重复提高效率)
        {
            int lac = find(now_query);                  //最近公共祖先就是查询点的father
            nodes[now].query_result[now_query] = lac;   //保存到当前点
            nodes[now_query].query_result[now] = lac;   //保存到被查询点
            nodes[now].queryed[now_query] = true;       //双向更新查询状态
            nodes[now_query].queryed[now] = true;
        }
    }
    return;
}

void output()   //依次查询
{
    while (!query_queue.empty())
    //依次取出被查询点
    {
        pair<int, int> q = query_queue.front();
        query_queue.pop();
        //直接输出
        cout << nodes[q.first].query_result[q.second] << endl;
    }
    return;
}

int main()
{
    init();
    Tarjan(root, root);
    output();
    return 0;
}