模板整合

自己认为模板在算法竞赛中还是比较重要的.
它能够帮助你快速的回忆起一种算法的框架
但OI的题目千变万化，模板只能做个参考

---

---

$tarjan$算法

求强联通分量

int dfn[N], low[N], scc[M], color[N];
stack <int> sta;
int time_cnt, scc_cnt;
void tarjan(int u) {
    dfn[u] = low[u] = ++time_cnt, sta.push(u);
    for (int i = hd[u]; i; i = e[i].nt) {
        int v = e[i].to;
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (!color[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt; 
        color[u] = scc_cnt;
        scc[scc_cnt]++;
        while (s.top() != u) {
            color[s.top()] = scc_cnt;
            scc[scc_cnt]++; sta.pop();
        } sta.pop();
    }
}

---

$DP$常用模板

背包

$01$背包问题：

for (int i = 1; i <= n; i++)
    for (int j = V; j >= v[i]; j--)
        dp[j] = max(dp[j], dp[j - v[i]] + c[i]);

完全背包：

for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= V; j++)
        dp[j] = max(dp[j], dp[j - v[i]] + c[i]);

多重背包：

for (int i = 1; i <= n; i++)
    for (int j = V; j >= v[i]; j--)
        for (int k = 0; k <= s[i]; k++)
            dp[j] = max(dp[j], dp[j - k * v[i]] + k * c[i]);

混合背包：

for (int i = 1; i <= n; i++) {
    if (p[i] == 0)
        for (int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
    else
        for (int k = 1; k <= p[i]; k++)
            for (int j = V; j >= v[i]; j--)
                dp[j] = max(dp[j], dp[j - v[i]] + c[i]);
}

二维背包：

for (int i = 1; i <= n; i++)
    for (int j = V; j >= v[i]; j--)
        for (int q = U; q >= u[i]; q--)
            dp[j][q] = max(dp[j][q], dp[j - v[i]][q - u[i]] + c[i]);

分组背包：

for (int k = 1; k <= t; k++)
    for (int j = V; j >= v[a[k][i]]; j--)
        for (int i = 1; i <= a[k][0]; i++)
            dp[j] = max(dp[j], dp[j - v[a[k][i]]] + c[a[k][i]]);

方案背包：

dp[0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = v[i]; j <= V; j++)
        dp[j] += dp[j - v[i]];

• 二进制优化：

    for(int i=1;i<=n;i++)
    {
        int x,y,s,t=1;
        scanf("%d%d%d",&x,&y,&s);
        while(s>=t)
        {
            v[nl++]=x*t;c[nl]=y*t;
            s-=t;
            t*=2;
        }
        v[nl++]=x*s;c[nl]=y*s;
    }

---

区间

for (int len = 2; len <= n; len++)
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        if (j > n) break;
        for (int k = l; k < r; k++)
            dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + w[l][r]);
    }

最长不下降子序列(LIS)

for (int i = n - 1; i >= 1; i--) {
    l = 0, k = 0;
    for (int j = i + 1; j <= n; j++)
        if (dp[j][1] > dp[i][1] && dp[j][2] > l)
            l = b[j][2];
    if (l > 0) b[i][2] = l + 1;
}
for (int i = 1; i <= n; i++)
    maxx = max(maxx, b[i][2]);

快读模板

---

快读实际上就是不断读入字符，而后转化数值处理，它要比$cin$和$scanf$快很多

inline int read() {  
    int s = 0, f = 1;  
    char ch = getchar();  
    while(!isdigit(ch)) {  
        if(ch == '-') f = -1;  
        ch = getchar();  
    }  
    while(isdigit(ch)) {  
        s = s * 10 + ch - '0';  
        ch = getchar();  
    }  
    return s * f;  
}  

• $isdigit$函数头文件$$

• 这里给出读入$int$类型时的模板，实际使用要根据数据范围改变函数类型

---

快写同理

inline void write(int x) {  
    if(x < 0) {  
        putchar('-');  
        x = -x;  
    }  
    if(x > 9)  
        write(x/10);  
    putchar(x % 10 - '0');  
    return;  
}

---

• 注意 在$VS$中使用$scanf$需要加#$define$ _CRT_SECURE_NO_WARNINGS这句话,所以快读快写在$VS$中会起到非常大的作用

最短路模板

---

Floyd

$$O(n^3)$$

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dis[i][j] > dis[i][k] + dis[k][j])
                dis[i][j] = dis[i][k] + dis[k][j];

Dijkstra(+STL堆优化)

$$O((n+m)logm)$$

void dijkstra(int start) {
    que.push(make_pair(0, start));
    dis[start] = 0;
    while (!que.empty()) {
        int tmp = que.top().second;
        que.pop();
        if (vis[tmp]) continue;
        vis[tmp] = true;
        for (int i = head[tmp]; i; i = edge[i].nxt) {
            int v = edge[i].to, w = edge[i].dis;
            if (!vis[v] && dis[v] > dis[tmp] + w)
                dis[v] = dis[tmp] + w,
                que.push(make_pair(-dis[v], v));
        }
    }
}

SPFA(Bellman-Ford队列优化)

$$O(nm)$$

void Spfa() {
    queue <int> que;
    dis[start] = 0;
    que.push(start);
    while (!que.empty()) {
        int tmp = que.front();
        que.pop(); vis[tmp] = false;
        for (i = head[tmp]; ~i; i = edge[i].nxt) {
            int v = edge[i].to, w = edge[i].dis;
            if (dis[v] < dis[tmp] + w) continue;
            dis[v] = dis[tmp] + w;
            if (!vis[v])
            vis[v] = true, que.push(v);
        }
    }
}