头像

TheSun

湖南大学




离线:1天前


最近来访(7)
用户头像
我要出去乱说
用户头像
xiusike1
用户头像
吃包子的小怪兽
用户头像
NatWist
用户头像
Alexshwing
用户头像
马老师的皮燕子

活动打卡代码 AcWing 90. 64位整数乘法

TheSun
6天前
#include <cstdio>

typedef long long LL;

LL qadd(LL a, LL b, LL p)
{
    LL res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    LL a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    printf("%lld\n", qadd(a, b, p));

    return 0;
}



活动打卡代码 AcWing 845. 八数码

TheSun
6天前
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int bfs(string start)
{
    //定义目标状态
    string end = "12345678x";
    //定义队列和dist数组
    queue<string> q;
    unordered_map<string, int> d;
    //初始化队列和dist数组
    q.push(start);
    d[start] = 0;
    //转移方式
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        //记录当前状态的距离,如果是最终状态则返回距离
        int distance = d[t];
        if(t == end) return distance;
        //查询x在字符串中的下标,然后转换为在矩阵中的坐标
        int k = t.find('x');
        int x = k / 3, y = k % 3;

        for(int i = 0; i < 4; i++)
        {
            //求转移后x的坐标
            int a = x + dx[i], b = y + dy[i];
            //当前坐标没有越界
            if(a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                //转移x
                swap(t[k], t[a * 3 + b]);
                //如果当前状态是第一次遍历,记录距离,入队
                if(!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                //还原状态,为下一种转换情况做准备
                swap(t[k], t[a * 3 + b]);
            }
        }
    }
    //无法转换到目标状态,返回-1
    return -1;
}

int main()
{
    string c, start;
    //输入起始状态
    for(int i = 0; i < 9; i++)
    {
        cin >> c;
        start += c;
    }

    cout << bfs(start) << endl;

    return 0;
}



活动打卡代码 AcWing 852. spfa判断负环

TheSun
7天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

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

//初始化邻接表
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa()
{
    queue<int> q;

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

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

        st[t] = false;

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

    memset(h, -1, sizeof h);

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

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

    return 0;

}




TheSun
7天前
#include<iostream>
#include<cstring>

using namespace std;

const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];

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

int find(int x)
{
    //遍历自己喜欢的女孩
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;//那x就预定这个女孩了
            //如果女孩j没有男朋友,或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
    //自己中意的全部都被预定了。配对失败。
    return false;
}

int main()
{
    memset(h,-1,sizeof h);

    cin>>n1>>n2>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    int res = 0;
    for(int i = 1; i <= n1; i ++)
    {  
        //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
        memset(st,false,sizeof st);
        if(find(i)) res++;
    }  

    printf("%d\n", res);

    return 0;
}




TheSun
7天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10; // 无向图, 所以最大边数是2倍
int e[M], ne[M], h[N], idx; // 使用邻接表
int st[N]; // 判断状态,是否 1 2 

// 初始化邻接表
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// dfs 来进行染色
bool dfs(int u, int color) {
    st[u] = color;  // 首先给这个点染色

    for(int i = h[u]; i != -1; i = ne[i]){  // 寻找相应的邻接表
        int j = e[i];
        if(!st[j]) {
            if(!dfs(j, 3 - color)) return false;
        }else if(st[j] == color) return false;
    }

    return true;
}

int main(){
    int n, m;
    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 = true;
    for(int i = 1; i <= n; i ++){
        if(!st[i]){
            if(!dfs(i, 1)){
                flag = false;
                break;
            }
        }
    }

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




TheSun
8天前

kruskal算法
基本思想:
将连通网中所有的边按照权值大小做升序排序,从权值最小的边开始选择,只要此边不和已选择的边一起构成环路,就可以选择它组成最小生成树。对于 N 个顶点的连通网,挑选出 N-1 条符合条件的边,这些边组成的生成树就是最小生成树。

基本步骤:
1. 将所有的边按照权重从小到大进行排序;
2. 枚举每条边a,b 和 权重 c, 如果不连通就把这条边加入到所存在的边的集合S
note:
存储边的时候可以用 结构体,但是需要重载小于号,需要用权重来判断。


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

using namespace std;

const int N = 100010, M = 200010;
int n, m;
int p[N];

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

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


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

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

    sort(edges, edges + m);

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

    int res = 0, cnt = 0;
    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)
        {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }

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

    return 0;
}



TheSun
9天前

Prim 算法– 基于贪心

思路:
dist[i]设置为无穷大
dist[1] = 0

for i in 0..n-1
1. 找到不在s集合中,距离s集合最近的点t
2. 将这个点t放入集合中
3. 利用这个点t, 更新不在集合s中的点

思路详解:
http://c.biancheng.net/algorithm/prim.html


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

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()
{
    scanf("%d%d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}



活动打卡代码 AcWing 851. spfa求最短路

TheSun
12天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

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

//初始化邻接表
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.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for(int i = h[t]; i != -1; 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;
                }
            }
        }
    }

    return dist[n];
}

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

    memset(h, -1, sizeof h);

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

    int t = spfa();

    if(t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);

    return 0;

}



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

TheSun
12天前
#include <cstring>
#include <algorithm>

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()
{
    scanf("%d%d%d", &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, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c); //保存最小的边
    }

    //处理询问
    floyd();

    //查询结果
    for(int i = 0; i < q; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        int t = d[a][b];
        if (t > INF / 2) puts("impossible"); //由于有负权边存在所以约大过INF/2也很合理
        else printf("%d\n", t);
    }

    return 0;
}




TheSun
12天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N];
int backup[N];

struct Edge
{
    int a;
    int b;
    int w;
}edges[M];

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


    for (int i = 0; i < k; i++) 
    {//k次循环

        memcpy(backup, dist, sizeof dist);

        for (int j = 0; j < m; j++) {//遍历所有边
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }

}

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

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

    bellman_ford();


    //if dist[n] > 最大数值的2倍
    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);




    return 0;
}