AcWing《Web应用课》拼团优惠！https://www.acwing.com/activity/content/introduction/1150/group_buy/134642/

AcWing《SpringBoot框架课》拼团优惠！https://www.acwing.com/activity/content/introduction/1877/group_buy/133496/

//两个点的集合编号是重合的，要给右半部分点的编号 统一加 n1 
#include<iostream>
#include<cstring>
using namespace std;
const int MAXM = 1e5 + 10, MAXN = 2 * 510;
int h[MAXM], e[MAXM], ne[MAXM], idx;
int n1, n2, m;
//st[]  在一次find(boy1) 中 产生了冲突 （即boy1看上的girl1已经和boy2匹配了）要让boy2再尝试find(boy2) 
//在find(boy2)过程中 就不能再去考虑girl1 所以要在find(boy2)之前标记一下st[girl1] = true;  
bool st[MAXN];//判重 不要重复搜一个点 
int match[MAXN];//记录右半部分和哪个左半部分的点匹配  match[girl] = boy

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

bool find(int boy)
{
    for(int i = h[boy];i != -1;i = ne[i])
    {
        int girl = e[i];
        if(!st[girl])
        {
            st[girl] = true;
            if(!match[girl] || find(match[girl])) //如果nv 没有和别的点匹配 或者 match[nv] 可以换成别的点 
            {

                match[girl] = boy;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n1 >> n2 >> m;
    for(int i = 0;i < m;i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b+n1); //只需要存左边到右边的边即可  右边的点加n1 
    }
    int ans = 0;//匹配成功的数量 
    for(int i = 1;i <= n1;i++) //遍历左半部分的点 
    {
        memset(st, false, sizeof st);
        if(find(i))//第i个点 找右半部分的点匹配 
        ans++;
    }
    cout << ans; 
    return 0;
}

//二分图就是可以将点划分到两个集合 使得所有的边都连接两个集合的点 即 集合内部没有边 边在集合之间 
//一个图是二分图当且仅当途中不含奇数环（环中边的数量是奇数 也即环中的点也是奇数） 

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 2e5 + 10;
int h[MAXN], e[MAXN], ne[MAXN], idx;
int n, m, color[MAXN];

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

bool dfs(int v, int c)
{
    color[v] = c;
    for(int i = h[v];i != -1;i = ne[i])
    {
        int nv = e[i];
        if(!color[nv]) //如果没有染色就染色 
        {
            //要染成和c不一样的颜色 3-c 
            if(!dfs(nv, 3 - c)) return false;
        }
        else//如果该点染上了颜色  就判断是否有矛盾 v和nv是否是同一种颜色 
        {
            if(color[nv] == c)
            {
                return false; //有矛盾 
            } 
        }
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 0;i < m;i++)
    {
        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)) //1代表一种颜色，2代表另一种颜色 
            {
                flag = false;
                break;
            }
        }
    }
    if(flag)
    cout << "Yes";
    else
    cout << "No";
    return 0;
} 

//y总 这里为什么一定重载小于号呢，是因为sort排序用的运算符是小于吗，我把重载改成大于 就报错了
//对滴，sort中用的都是小于号。
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 2 * 1e5 + 10;
struct Edge{
    int a;
    int b;
    int c;
} edge[MAXN];
int n, m;
int p[MAXN];
//如果cmp返回结果为假, 那么函数就会将他们互换位置；

//如果cmp返回结果为真，就会保持原来位置不变。
bool cmp(struct Edge& e1, struct Edge& e2)
{
    return e1.c < e2.c;
}

int find(int a)
{
    if(p[a] != a)
    {
        p[a] = find(p[a]);
    }
    return p[a];
}
int kruskal()
{
    sort(edge, edge+m,cmp);
    for(int i = 0;i <= n;i++)
    p[i] = i;
    int cnt = 0;//记录加入最小生成树中边的数量 
    int sum = 0;
    for(int i = 0;i < m;i++)//按边的权重从小到大遍历边 
    {
        int a = edge[i].a, b = edge[i].b, c = edge[i].c;
        int pa = find(a), pb = find(b);
        //如果边的两个端点不在同一个连通块 那就合并这两个连通块  并将这条边加入最小生成树中 
        if(pa != pb)
        {
            p[pa] = pb;
            sum += c;
            cnt++;
        }
    }
    if(cnt == n-1) //最小生成树有n-1条边。 
    return sum;
    else
    return -1; 
}
int main()
{
    cin >> n >> m;
    for(int i = 0;i < m;i++)
    {
        cin >> edge[i].a >> edge[i].b >> edge[i].c;
    }
    int ans = kruskal();
    if(ans == -1)
    cout << "impossible";
    else
    cout << ans;
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 510, inf = 0x3f3f3f3f;
int g[MAXN][MAXN], dist[MAXN];
int n, m;
bool st[MAXN];
int prim()
{
    memset(dist, inf, sizeof dist);
    dist[1] = 0;
    int sum = 0;
    for(int i = 0;i < n;i++)
    {
        int v = -1;
        for(int j = 1;j <= n;j++)
        {
            if(!st[j] && (v == -1 || dist[j] < dist[v]))
            v = j;
        }
        if(dist[v] == inf)
        return inf;
        st[v] = true;
        sum += dist[v]; 
        for(int j = 1;j <= n;j++)
        {
            if(!st[j] && g[v][j] != inf && dist[j] > g[v][j])
            {
                dist[j] = g[v][j];
            }
        }
    }
    return sum;
}
int main()
{
    memset(g, inf, sizeof g);
    cin >> n >> m;
    for(int i = 0;i < m;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int ans = prim();
    if(ans == inf)
    cout << "impossible";
    else
    cout << ans;
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 210;
const int inf = 0x3f3f3f3f;
int d[MAXN][MAXN];
int n, m, q;
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()
{
    //memset(d, inf, sizeof d);
    cin >> n >> m >> q;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if(i == j)//到自己的距离是0 
            d[i][j] = 0;
            else
            d[i][j] = inf;
        }
     } 
    for(int i = 0;i < m;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c); 
    }
    Floyd();
    while(q--)
    {
        int a, b;
        cin >> a >> b;
        if(d[a][b] > inf / 2) 
        //因为存在负权边所以如果两个点之间没有通路  但这两个点的距离可能比inf小一些 
        {
            cout << "impossible" << endl;
        }
        else
        cout << d[a][b] << endl;
    }
    return 0;
 } 

//①存在点入队的次数超过n-1就说明有负环
//②某条最短路径上的点的个数超过n就说明有环 
/*
存在着某一个源点不可达的负环  所以要让每一个点都充当源点才能看出图中是否存在负环 也即每个点当作源点执行一遍spfa()
但这样太慢会超时 ！！！
可以这样想添加一个虚拟的点x，x到每个点都是可达的 且 边的权重是0  将x当作唯一源点 从x开始找负环 那么可定是可达的
dist[]表示其他所有点到x的最短路 
*/
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 2010;
const int MAXM = 10010;
int h[MAXM], e[MAXM], w[MAXM], ne[MAXM], idx;
int n, m;
bool st[MAXN];
int dist[MAXN], cnt[MAXN];
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

bool spfa()
{
    queue<int> q;
    for(int i = 1;i <= n;i++)
    {
        q.push(i);
        st[i] = true;
    }
    while(!q.empty())
    {
        int v = q.front();
        q.pop();
        st[v] = false;
        for(int i = h[v];i != -1;i = ne[i])
        {
            int nv = e[i];
            if(dist[nv] > dist[v] + w[i])
            {
                dist[nv] = dist[v] + w[i];
                cnt[nv] = cnt[v] + 1;
                if(cnt[nv] > n)
                {
                    return true; //有环 
                }
                if(!st[nv])
                {
                    q.push(nv);
                    st[nv] = true;
                }
            }
        }
    }
    return false; 
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 0;i < m;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if(spfa())
    cout << "Yes";
    else
    cout << "No";
    return 0;
}