头像

ShyWind




离线:7天前


最近来访(0)


ShyWind
1个月前
//这里填你的代码^^
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N]; //这道题是稠密图,适合用邻接矩阵存储
int dist[N];//Dijkstra算法中的灵魂选手,可更新的距离
int st[N];//是否确定最终的最短路径||dist[i]是否是最终值

int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 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;

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

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

int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);//有重边,取较小的边
    }
    cout << dijkstra();
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



ShyWind
1个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;

int h[N], e[N], ne[N], idx;
int d[N];//in degree
int q[N];

void add(int a, int b){//add edge a -> b
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
bool topsort(){
    int hh = 0, tt = -1;//init queue 

    for(int i = 1; i <= n; i ++){
        if(!d[i]) q[++tt] = i;
    }

    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(-- d[j] == 0) 
                q[++ tt] = j;
        }
    }
    return tt == n - 1;
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m;
    int a, b;
    while(m --){
        cin >> a >> b;
        add(a, b);
        ++ d[b];
    }

    if(!topsort()) cout << -1;
    else for(int i = 0; i < n; i ++) cout << q[i] << " ";

    return 0;
}


活动打卡代码 AcWing 842. 排列数字

ShyWind
1个月前
#include<iostream>

using namespace std;

const int N = 7;
int path[N], n;
bool sta[N];

void dfs(int h){
    if(h == n){
        for(int i = 0; i < n; i ++) printf("%d ", path[i]);
        puts("");
    }

    for(int i = 1; i <= n;  i ++){
        if(!sta[i]){
            path[h] = i;
            sta[i] = true;
            dfs(h + 1);
            sta[i] = false;
        }
    }
}

int main(){
    cin >> n;
    dfs(0);
    return 0;
}


活动打卡代码 AcWing 847. 图中点的层次

ShyWind
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 100010;

int h[N], e[N], ne[N], idx;
int n, m;
int d[N];

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

int bfs(){
    memset(d, -1, sizeof d);

    queue<int> q;
    q.push(1);
    d[1] = 0;

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

        for(int i = h[t]; i != -1; i = ne[i]){
            int j =e[i];
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    return d[n];
}

int main(){
    cin >> n >> m;
    int a, b;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        cin >> a >>b;
        add(a, b);
    }
    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 846. 树的重心

ShyWind
1个月前
树和图的深度优先搜索算法模板

dfs用递归实现,相对bfs代码较短,因为系统维护了栈,但是bfs是要在代码里维护一个队列

void dfs(int u){
    visit();//访问逻辑 上来就写 如cout...
    st[u] = true;

    for(int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j]) dfs(j); //j结点(是一个与u连接的结点)未被访问过,则对之进行深度优先搜索
    }//这几行是逻辑控制语句
}




活动打卡代码 AcWing 844. 走迷宫

ShyWind
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

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

int bfs(){
    queue<PII> q;

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    q.push({0,0});

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

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

        for(int i = 0; i < 4; i ++){
            int x = t.first + dx[i], y = t.second + dy[i];

            if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
            }
        }
    }

    return d[n-1][m-1];
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cin >> g[i][j];
    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 843. n-皇后问题

ShyWind
1个月前

#include<iostream>

using namespace std;

const int N = 20;

int path[N], n;
bool col[N], udl[N], ddl[N];

void print_ans(){
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++){
            if(j != path[i]) cout << '.';
            else cout << 'Q';
        }
        puts("");
    }
    puts("");
}

void dfs(int l){
    if(l == n){
        print_ans();
        return;
    }

    for( int i = 1; i <= n; i ++ ){
        if(!col[i] && !udl[l + n + 1 - i] && !ddl[l + i]){
            path[l + 1] = i;
            col[i] = udl[l + n + 1 - i] = ddl[l + i] = true;
            dfs(l + 1);
            col[i] = udl[l + n + 1 - i] = ddl[l + i] = false;
        }
    }
}

int main(){
    cin >> n;
    dfs(0);
    return 0;
}






活动打卡代码 AcWing 840. 模拟散列表

ShyWind
1个月前
#include<iostream>
#include<cstring>

const int N = 100003;

int h[N], e[N], ne[N], idx;

void insert(int x){
    int k = (x % N + N) % N;//让余数变为正数

    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx;
    idx ++;
}

bool find(int x){
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i]){
        if(e[i] == x)
            return true;
    }
    return false;
}

int main(){
    int n;
    scanf("%d", &n);
    memset(h, -1, sizeof h);//全部是空指针

    while(n --){
        char op[2];
        int x;
        scanf("%s%d", op, &x);

        if(*op == 'I') insert(x);
        else {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}



ShyWind
1个月前
//这里填你的代码^^
#include<iostream>

using namespace std;

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

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

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++){
        p[i] = i;
        q[i] = 1;
    }
    string op;
    while(m --){
        cin >> op;
        if(op == "C"){
            int a, b;
            scanf("%d%d", &a, &b);
            // if(find(a)!=find(b)){
            //   q[find(b)] += q[find(a)];
            //     p[a] = find(b); 
            // }
            a = find(a), b = find(b);
            if (a != b)
            {
                p[a] = b;
                q[b] += q[a];
            }
        }else if(op == "Q1"){
            int a, b;
            scanf("%d%d", &a, &b);
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }else{
            int a;
            scanf("%d", &a);
            printf("%d\n", q[find(a)]);
        }
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 836. 合并集合

ShyWind
1个月前
#include<iostream>

using namespace std;

const int N = 100010;

int n, m;
int p[N];

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

int main(){
    scanf("%d%d",&n,&m);
    char op[2];
    for(int i = 0; i < n; i ++) p[i] = i;
    while(m--){
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(*op == 'M') p[find(b)] = find(a);
        else {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}