浩然正气

关注数

粉丝数

阅读量

3869

+关注发消息

在线

最近来访(141)

wangsyCHN

ji_suan_ji

Coinisi.

Yuzhao_Li

陈律全_1

ssy_

爱上AC

我们仨

龙晨薇

yao4246

Benny_TRY

相静.

骏杰

o樱桃小完犊子o

Amyer

金属

桂花煮柚子

啊冰

阳光假日不阳光

笔墨春秋

活动打卡代码 AcWing 861. 二分图的最大匹配

浩然正气
1天前

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

using namespace std;

const int N = 200010;

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

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

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

int main()
{
    int res = 0;
    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);
    }

    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, false, sizeof st);
        if (find(i))
            res += 1;
    }
    printf("%d\n", res);
    return 0;
}

            

活动打卡代码 AcWing 860. 染色法判定二分图

浩然正气
1天前

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

using namespace std;

const int N = 200010;

int n, m;
bool st[N];
int color[N];
int h[N], e[N], ne[N], idx;

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

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

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

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

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

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

    if (!flag)
        puts("Yes");
    else
        puts("No");
    return 0;
}

            

活动打卡代码 AcWing 859. Kruskal算法求最小生成树（算法基础课）

浩然正气
1天前

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

using namespace std;

const int N = 200010;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;
    bool operator <(const Edge &W)const{
        return w < W.w;
    }
}edge[N];

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

int kruskal()
{
    int res = 0, cnt = 0;
    sort(edge, edge + m);

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

    for (int i = 0; i < m; i ++ )
    {
        int a = edge[i].a;
        int b = edge[i].b;
        int w = edge[i].w;

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

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

    if (cnt < n - 1)
        return 0x3f3f3f3f;
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edge[i] = {a, b, w};
    }
    int res = kruskal();
    if (res == 0x3f3f3f3f)
        puts("impossible");
    else
        printf("%d\n", res);
    return 0;
}


            

活动打卡代码 AcWing 858. Prim算法求最小生成树（算法基础课）

浩然正气
1天前

include [HTML_REMOVED]

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

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

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

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)
        res += dist[t];

    if (i && (dist[t] == INF))
        return INF;

    for (int j = 1; j <= n; j ++ )
        dist[j] = min(dist[j], g[t][j]);
    st[t] = true;
}
return res;

}

int main()
{
scanf(“%d%d”, &n, &m);
memset(g, 0x3f, sizeof g);
while (m – )
{
int u, v, w;
scanf(“%d%d%d”, &u, &v, &w);
g[u][v] = g[v][u] = min(g[u][v], w);
}

int res = prim();
if (res == INF)
    puts("impossible");
else
    printf("%d\n", res);
return 0;

}

活动打卡代码 AcWing 854. Floyd求最短路（算法基础课）

浩然正气
1天前

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

using namespace std;

const int N = 510, INF = 1e9;

int n, m, k;
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()
{
    scanf("%d%d%d", &n, &m, &k);
    /**进行初始化**/
    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, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }
    floyd();

    while (k -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (d[x][y] > INF / 2)
            puts("impossible");
        else
            printf("%d\n", d[x][y]);
    }
    return 0;
}

            

活动打卡代码 AcWing 852. spfa判断负环（算法基础课）

浩然正气
1天前

                /**4、spfa算法判断负环**/
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 500010;

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

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

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

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

    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                cnt[j] = cnt[t] + 1;
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
                if (cnt[j] >= n)
                    return true;
            }
        }
    }

    return false;
}

int main()
{
    int a, b, c;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

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

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

            

活动打卡代码 AcWing 859. Kruskal算法求最小生成树

浩然正气
1天前

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

using namespace std;

const int N = 200010;

int n, m;
int p[N];

struct Edge
{
    int a, b, w;
    bool operator <(const Edge &W)const{
        return w < W.w;
    }
}edge[N];

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

int kruskal()
{
    int res = 0, cnt = 0;
    sort(edge, edge + m);

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

    for (int i = 0; i < m; i ++ )
    {
        int a = edge[i].a;
        int b = edge[i].b;
        int w = edge[i].w;

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

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

    if (cnt < n - 1)
        return 0x3f3f3f3f;
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edge[i] = {a, b, w};
    }
    int res = kruskal();
    if (res == 0x3f3f3f3f)
        puts("impossible");
    else
        printf("%d\n", res);
    return 0;
}

            

活动打卡代码 AcWing 858. Prim算法求最小生成树

浩然正气
1天前

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

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

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


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

    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)
            res += dist[t];

        if (i && dist[t] == INF)
            return INF;

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
        st[t] = true;
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    int t = prim();
    if (t == INF)
        puts("impossible");
    else
        printf("%d\n", t);
    return 0;
}

            

分享图论阶段复习--最短路

浩然正气
3天前

                一、单源最短路

堆优化版的Dijkstra算法

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

using namespace std;

const int N = 500010;
typedef pair<int, int> PII;
#define x first
#define y second

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

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});

    while (!q.empty())
    {
        auto t = q.top();
        q.pop();

        int id = t.y, d = t.x;
        if (st[id] == true)
            continue;
        st[id] = true;

        for (int i = h[id]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > d + w[i])
            {
                dist[j] = d + w[i];
                q.push({dist[j], j});
            }
        }
    }

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

int main()
{
    int a, b, c;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

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

    int res = dijstra();
    printf("%d\n", res);
    return 0;
}



有边权限制的最短路算法：bellman_ford

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

using namespace std;

const int N = 500010;

int n, m, k;
bool st[N];
int dist[N];
int copys[N];

struct Edge
{
    int a, b, w;
}edge[N];

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

    for (int i = 1; i <= k; i ++ )
    {
        memcpy(copys, dist, sizeof dist);
        for (int j = 1; j <= m; j ++ )
        {
            int a = edge[j].a;
            int b = edge[j].b;
            int w = edge[j].w;
            dist[b] = min(dist[b], copys[a] + w);
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2)
        return -1;
    return dist[n];
}

int main()
{
    int a, b, w;
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 1; i <= m; i ++ )
    {
        scanf("%d%d%d", &a, &b, &w);
        edge[i] = {a, b, w};
    }

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



spfa算法求最短路

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

using namespace std;

const int N = 500010;

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

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

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

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[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()
{
    int a, b, c;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

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

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



spfa算法判断负环

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

using namespace std;

const int N = 500010;

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

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

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

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

    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                cnt[j] = cnt[t] + 1;
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
                if (cnt[j] >= n)
                    return true;
            }
        }
    }

    return false;
}

int main()
{
    int a, b, c;
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

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

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


二、多元汇最短路

floyd算法：适用于多元汇最短路

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

using namespace std;

const int N = 510, INF = 1e9;

int n, m, k;
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()
{
    scanf("%d%d%d", &n, &m, &k);
    /**初始化**/
    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;
        scanf("%d%d%d", &a, &b, &w);
        d[a][b] = min(d[a][b], w);
    }
    floyd();

    while (k -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (d[x][y] > INF / 2)
            puts("impossible");
        else
            printf("%d\n", d[x][y]);
    }
    return 0;
}

            

活动打卡代码 AcWing 854. Floyd求最短路

浩然正气
3天前

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

using namespace std;

const int N = 510, INF = 1e9;

int n, m, k;
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()
{
    scanf("%d%d%d", &n, &m, &k);
    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;
        scanf("%d%d%d", &a, &b, &w);
        d[a][b] = min(d[a][b], w);
    }

    floyd();

    while (k -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (d[x][y] > INF / 2)
            puts("impossible");
        else
            cout << d[x][y] << endl;
    }

    return 0;
}

            