url: https://www.luogu.com.cn/problem/P3110

tag:
USACO14DEC，最短路，bfs，USACO，2014

思路：
求三遍最短路，分别是正着求Bessie 和 Elsie 到每个点的最短路，和逆着求终点n到每个点的最短路，然后枚举看从哪个点开始一起走（Bessie 可以背着 Elsie 走）然后到终点的能量最小，更新ans。最后输出ans即可。

代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int B, E, P, n, m;
int idx, e[N], ne[N], h[N], w[N];
int distB[N], distE[N], distP[N];
bool st[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = 1;
    h[a] = idx ++;
}
void dijkstra(int s, int dist[])
{
    memset(st, 0, sizeof st);
    dist[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});

    while (!heap.empty())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    memset(distE, 0x3f, sizeof distE);
    memset(distB, 0x3f, sizeof distB);
    memset(distP, 0x3f, sizeof distP);
    cin >> B >> E >> P >> n >> m;
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dijkstra(1, distB);
    dijkstra(2, distE);
    dijkstra(n, distP);
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i ++)
    {
        ans = min(ans, B * distB[i] + E * distE[i] + P * distP[i]);
    }
    cout << ans;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1120

tag:
枚举，搜索，剪枝，dfs

思路：
先从大到小排序，并计算全部木棍长度的和。之后从最长的木棍长开始一直到和的一半枚举，作为原来木棍的长度。然后拿到这个原来的长度之后dfs一下看在有限段的情况下能不能拼凑出全部木棍，可以就输出。最后枚举完全部可能结果后都没答案，就输出长度和作为结果，表示原来只有一根木棍。参考： https://www.luogu.com.cn/article/fxoshw2y

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 70;
int n, len, m, sum;
int a[N];
int nxt[N];
bool flag = false;
bool st[N];
bool cmp (int &a, int &b)
{
    return a > b;
}
void dfs(int k, int last, int rest)
{
    int i;
    if (!rest) {
        if (k == m)
        {
            flag = true;
            return;
        }
        for (i = 0; i < n; i ++) if (!st[i]) break;
        st[i] = true;
        dfs(k + 1, i, len - a[i]);
        st[i] = false;
        if (flag) return;
    }
    int l = last + 1, r = n - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (a[mid] <= rest) r = mid;
        else l = mid + 1;
    }
    for (i = l; i < n; i ++)
    {
        if (!st[i])
        {
            st[i] = true;
            dfs(k, i, rest - a[i]);
            st[i] = false;
            if (flag) return;

            if (rest == a[i] || rest == len) return;
            i = nxt[i];
            if (i == n - 1) return;
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sort(a, a + n, cmp);
    nxt[n - 1] = n;
    for (int i = n - 2; i >= 0; i --)
    {
        if (a [i] == a[i + 1]) nxt[i] = nxt[i + 1];
        else nxt[i] = i;
    }
    for (len = a[0]; len <= sum / 2; len ++)
    {
        if (sum % len != 0) continue;
        m = sum / len;
        st[0] = true;
        dfs(1, 0, len - a[0]);
        st[0] = false;
        if (flag)
        {
            cout << len << endl;
            return 0;
        }
    }
    cout << sum << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P4667

tag:
BalticOI 2011，最短路，双端队列，bfs

思路：
用双端队列的bfs，每次走到下一步的时候判断方向是否相同，相同且更新之后路径变小就插到队列前面，不同且更新之后路径变小就插到队列后面。判断是否无解就判断一下终点横纵坐标和是否为奇数，为奇数就无解，因为起点和终点的横纵坐标奇偶性相同（沿对角线走）。
参考： https://www.luogu.com.cn/article/d1fliiql

代码：

#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
const int N = 550;
const int dx[4] = {1, -1, -1, 1};
const int dy[4] = {1, 1, -1, -1};
const char a[5] = "\\/\\/";
const int ix[4] = {0, -1, -1, 0};
const int iy[4] = {0, 0, -1, -1};
deque<int> x;
deque<int> y;
int n, m;
char d[N][N];
int vis[N][N];

void bfs()
{
    memset(vis, 0x3f, sizeof vis);
    x.push_back(0);
    y.push_back(0);
    vis[0][0] = 0;
    while (!x.empty()) {
        int xx = x.front();
        int yy = y.front();
        x.pop_front();
        y.pop_front();
        for (int i = 0; i < 4; i++) {
            int dnx = xx + dx[i];
            int dny = yy + dy[i];
            int inx = xx + ix[i];
            int iny = yy + iy[i];
            if (dnx >= 0 && dnx <= n && dny >= 0 && dny <= m) {
                if (a[i] != d[inx][iny]) {
                    int t = vis[xx][yy] + 1;
                    if (t < vis[dnx][dny]) {
                        x.push_back(dnx);
                        y.push_back(dny);
                        vis[dnx][dny] = t;
                    }
                } else {
                    int t = vis[xx][yy];
                    if (t < vis[dnx][dny]) {
                        x.push_front(dnx);
                        y.push_front(dny);
                        vis[dnx][dny] = t;
                    }
                }
            }
        }
    }
    cout << vis[n][m] << endl;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> d[i];
    if ((n + m) % 2) cout << "NO SOLUTION" << endl;
    else bfs();
    return 0;
}

url: https://www.luogu.com.cn/problem/P1119

tag:
图论，枚举，最短路

思路：
这道题可以用floyd算法来做，每次询问，都将当前这个时间可以重建完的村庄用floyd算法更新一下所有点的最短路。最后判断一下这个询问的两个村庄是否重建完以及是否可以联通，如果重建完并且联通就输出最短路，否则输出-1

代码：

#include <iostream>
#include <vector>
using namespace std;
const int N = 220;
int n, m, q;
int f[N][N];
int a[N];

inline void update(int k)
{
    for (int i = 0; i < n; i ++)
        for (int j = 0;  j< n; j ++)
            f[i][j] = f[j][i] = min(f[i][j], f[i][k] + f[k][j]);
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < n; j ++) f[i][j] = 0x3f3f3f3f;
        f[i][i] = 0;
    }
    for (int i = 0; i < m; i ++)
    {
        int x, b, w;
        cin >> x >> b >> w;
        f[x][b] = f[b][x] = w;
    }
    cin >> q;
    int idx = 0;
    for (int i = 0; i < q; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        while (a[idx] <= z && idx < n)
        {
            update(idx);
            idx ++;
        }
        if (a[x] > z || a[y] > z) cout << -1 << endl;
        else if (f[x][y] == 0x3f3f3f3f) cout << -1 << endl;
        else cout << f[x][y] << endl;
    }
    return 0;
}

url: https://www.luogu.com.cn/problem/P2195

tag:
树的直径，树形DP，dfs，搜索，并查集，图论

思路：
先用树形DP求出每棵树的直径，并用并查集维护联通情况。用数组c来维护树的直径。对于询问1，直接输出直径，对于询问2，如果不在一个集合中，直径可能是原来两棵树的直径和 + 1，和原来两棵树的直径取一个最大值。参考： https://www.luogu.com.cn/article/o2yhg6cs

代码：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 3e5 + 20;
int n, m, q, len;
int d[N], g[N];
int f[N], c[N];
vector<int> e[N];
bool st[N];
int find(int x)
{
    if (f[x] != x) return f[x] = find(f[x]);
    return x;
}
void dfs(int x, int fa)
{
    int m1 = -1, m2 = -1;
    for (int i = 0; i < e[x].size(); i ++)
    {
        int y = e[x][i];
        if (y == fa) continue;
        dfs(y, x);
        int tmp = d[y] + 1;
        d[x] = max(d[x], tmp);
        if (tmp > m1) m2 = m1, m1 = tmp;
        else if (tmp > m2) m2 = tmp;
    }
    g[x] = max(max(0, m1 + m2), max(m1, m2));
    len = max(len, g[x]);
}
void calc(int x)
{
    len = 0;
    dfs(x, 0);
    c[x] = len;
}
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++) f[i] = i;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        f[find(a)] = find(b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for (int i = 1; i <= n; i ++)
    {
        if (f[i] != i || st[i]) continue;
        calc(i);
        st[i] = 1;
    }
    while (q --)
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1)
        {
            printf("%d\n", c[find(x)]);
            continue;
        }
        int y;
        scanf("%d", &y);
        x = find(x), y = find(y);
        if (x == y) continue;
        int tmp = ((c[x] + 1) >> 1) + ((c[y] + 1) >> 1) + 1;
        tmp = max(tmp, max(c[x], c[y]));
        f[find(x)] = find(y);
        c[find(x)] = tmp;
    }
    return 0;
}