头像

麋鹿是森林的眼睛




离线:6天前



#include<iostream>
#include<algorithm>
using namespace std;

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

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

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

int kru(){
    sort(edge,edge + 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= edge[i].a, b = edge[i].b, w = edge[i].w;
        a = find(a), b = find(b);

        if(a != b){
            p[a] = b;
            res += w;
            cnt++;
        }
    }
    if(cnt < n - 1)return INF;
    return res;
}


int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i < m; i ++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edge[i] = {a,b,c};
    }
    int t= kru();

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

    return 0;

}



#include<iostream>
#include<cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int g[N][N];
int dist[N];
int n, m;
bool st[N];
int ans = 0;
int prim(){
    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;
        }
        st[t] = true;
        if(dist[t] == INF)return INF;
        if(i)ans += dist[t];

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

int main(){
    memset(g,0x3f,sizeof g);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++){
        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 854. Floyd求最短路

#include<iostream>
#include<cstring>
using namespace std;

const int N = 210, M = 20010, INF = 1e9;
int g[N][N];
int n,m,k;

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

int main(){
    scanf("%d%d%d",&n,&m,&k);
    //memset(g, 0x3f, sizeof g);
    for(int i = 0; i <= n; i ++){
        for(int j = 0; j <= n; j ++){
            if(i == j)g[i][j] = 0;
            else g[i][j] = INF;
        }
    }
    for(int i = 0; i < m; i ++){
        int a, b, c;
        scanf("%d%d%d",&a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    floyd();

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

        int t = g[a][b];
        if(t > 0x3f3f3f3f / 2) puts("impossible");
        else printf("%d\n", t);
    }

    return 0;
}



RT




RT



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

#include<iostream>
#include<cstring>
using namespace std;

const int N = 100010, M = N * 2;

int h[N], e[M], ne[M], idx;
int ans = N;
int n;
bool st[N];

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

int dfs(int u){
    st[u] = true;

    int size = 0, sum = 0;
    for(int i = h[u]; i != -1; i = ne[i]){

        int j = e[i];
        if(st[j])continue;

        int s = dfs(j);
        size = max(size, s);
        sum += s;
    }

    size = max(size, n - sum - 1);
    ans = min(ans, size);

    return sum + 1;
}

int main(){
    scanf("%d",&n);
    memset(h, -1, sizeof h);
    for(int i = 0; i < n; i ++){
        int a,b;
        scanf("%d%d", &a, &b);
        add(a, b),add(b, a);
    }
    dfs(1);
    printf("%d", ans);
}


活动打卡代码 AcWing 885. 求组合数 I

#include<iostream>
using namespace std;

const int N = 2010, mod = 1e9 + 7;

int c[N][N];
int n;

void init(){
    for(int i = 0; i < N; i ++)
        for(int j = 0; j <= i; j++){
            if(!j)c[i][j] = 1;
            else{
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
            }
        }
}

int main(){
    scanf("%d", &n);
    init();
    while(n --){
        int a,b;
        scanf("%d%d",&a, &b);
        printf("%d\n", c[a][b]);
    }

    return 0;
}


活动打卡代码 AcWing 878. 线性同余方程

#include<iostream>
using namespace std;
typedef long long LL;

int n;

int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y -= a / b * x;
    return d;
}

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

    while(n--){
        int a, b, m, x, y;
        scanf("%d%d%d", &a, &b, &m);
        int d = exgcd(a, m, x, y);
        if(b % d)puts("impossible");
        else{
            printf("%d\n", (LL)x * (b / d) % m);
        }
    }

    return 0;
}



#include<iostream>
using namespace std;

int n, a, b;

void exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return;
    }

    exgcd(b, a%b, y, x);
    y -= a / b * x;
}

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

    while(n --){
        int x, y;
        scanf("%d%d", &a, &b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x, y);
    }

    return 0;
}


活动打卡代码 AcWing 876. 快速幂求逆元

#include<iostream>
using namespace std;

typedef long long LL;

int pmi(int a, int b, int p){
    int res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % p;
        b >>= 1;
        a = (LL)a * a % p; 
    }

    return res;
}

int main(){
    int n ;
    scanf("%d", & n);
    while(n --){
        int a,p;
        scanf("%d%d",&a, &p);
        if(a % p == 0)puts("impossible");
        else printf("%d\n" , pmi(a, p - 2, p));
    }

    return 0;
}