#include <iostream>
#include <algorithm>

// 在背包装得下时，背包内总物品的价值最高是多少？
// 1、0 1背包问题：每件物品最多只能用一次
// 2、完全背包问题：每件物品无限次使用
// 3、多重背包问题：每个物品最多有si个
//      -- 优化版
// 4、分组背包问题：有N组物品 限制条件

// Dp —— 状态表示 f(i,j) —— 集合：所有只考虑前i个物品，且体积不超过j的集合
//                       —— 属性：集合当中每个方案的最大价值
//    —— 状态计算 —— 集合划分 选不选第i个物品(不重不漏)
//                       —— 所有不选第i个物品的方案
//                       —— 所有选择第i个物品的方案
using namespace std;

const int N = 1010;

int n, V;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> V;

    for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; // 输入体积和价值

    for (int i = 1; i <= n; i ++)// i是前ige物品
        for (int j = V; j >= v[i]; j --)// j是枚举的体积
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[V];


    return 0;
}

``

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 510, M = 1e5 + 10;

int n1, n2, m;
int h[N], val[M], ne[M], idx;
int match[N];
bool st[N];

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

bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = val[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}

return false;

}

int main()
{
scanf(“%d%d%d”, &n1, &n2, &m);

memset(h, -1, sizeof h);

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

    add(a, b);
}

int res = 0;
for (int i = 1; i <= n1; i ++)
{
    memset(st, false, sizeof st);
    if (find(i)) res ++;
}

cout << res << endl;

return 0;

}
```

#include <iostream>

using namespace std;

const int N = 1010;

int q[N];

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i ++) cin >> q[i];

    int res = 0;
    for (int i = 1; i <= n - 2; i ++)
    {
        if (q[i - 1] > q[i] && q[i + 1] > q[i]) res ++;
        if (q[i - 1] < q[i] && q[i + 1] < q[i]) res ++;
    }

    cout << res << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
// 一个图是二分图，当且仅当图当中不含有奇数环
// 由于没有奇数环，所有染色过程没有矛盾
// 1 -- 2 -- 1 -- 2
//   -- 2 -- 1 -- 2 -- 1 -- 2
//   -- 2 -- 1

// 染色法：
//  1、for (i = 1;i <= n; i ++)
//         if i 未染色
//              dfs(i,1) 把i的所有连通块染色
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int h[N], idx, val[M], ne[M];
int color[N]; // 表示染色

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

bool dfs(int u, int c)
{
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = val[i];
        if (!color[j])
        {
            if (!dfs(j, 3 - c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m --)
    {
        int a, b;
        cin >> a >> b;

        add(a, b), add(b, a);
    }

    bool flag = true;
    for (int i = 1; i <= n; i ++)
        if (!color[i])
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }

    if (flag) puts("Yes");
    else puts("No");

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
// 稀疏图
// 1、先将所有边按权重从小到大排序 O(mlogm)
// 2、枚举每一条边a--b权重是c
//      if a,b不连通
//          将这条边加入集合中
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int n, m;
int father[N];

struct Edge
{
    int a, b, w;

    bool operator< (const Edge &W) const
    {
        return w < W.w;
    }
}edges[M];

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

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i ++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++) father[i] = i;

    int res = 0, cnt = 0;// res最小生成树当中所有树边的权重之和 cnt存当前加了的边
    for (int i = 0; i < m; i ++)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);

        if (a != b)
        {
            father[a] = b;
            res += w;
            cnt ++;
        }
    }

    if (cnt < n - 1) puts("impossible");
    else printf("%d\n", res);


    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

// 朴素Prim算法
// dist[t]初始化为正无穷
// 集合：当前已经在连通块中的所有点
// for (n次迭代)
//    t <- 找到集合外距离最近的点
//    用t更新其他点到集合的距离
//    st[t] = true;
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++)
    {
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;// 不连通

        if (i) res += dist[t];
        for (int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], g[t][j]);

        st[t] = true;
    }

    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);   
    cin >> n >> m;

    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;

        g[a][b] = g[b][a] = min(g[a][b], c);// 图的存储
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else cout << t << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>

// 邻接矩阵存

// d[k, i , j] k是阶段 d[k,i,j] = d[k-1,i,k] + d[k-1,k,j];
// for (int k = 1; k <= n; k ++)
//      for (int i = 1; i <= n; i ++)
//          for (int j = 1; j <= n; j ++)
//              d[i, j] = min(d[i, j], d[i, k] + d[k, j])
// d(i, j) 存的是i->j最短路的长度

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    cin >> n >> m >> Q;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

    while (m --)
    {
        int a, b, w;
        cin >> a >> b >> w;

        d[a][b] = min(d[a][b], w);
    }

    floyd();

    while (Q --)
    {
        int a, b;
        cin >> a >> b;

        if (d[a][b] >= INF / 2) puts("impossible");
        else cout << d[a][b] << endl;;
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 10010;

int n, m;
int dist[N], cnt[N];
bool st[N];
int h[N], idx, val[N], w[N], ne[N];

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

bool spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++)
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = val[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}


int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

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

        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");   

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

// spfa算法是对bellman-ford算法的优化
// 一个点如果没有被更新过，就不需要用它来更新后面的点的距离 队列里存放待更新的点

using namespace std;

const int N = 1e5 + 10;

int n, m;
int dist[N];
int h[N], w[N], val[N], ne[N], idx;
bool st[N];

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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true; //防止队列中存重复的点

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;// 点从队列中出来就删除

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = val[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                    q.push(j);
                    st[j] = true;
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m --)
    {
        int a, b, c;
        cin >> a >> b >> c;

        add(a, b, c);
    }

    int res = spfa();

    if (res == -1 && dist[n] != -1) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}