头像

有猷

姜堰四中




离线:7天前



有猷
14天前

请问 $严格次小生成树$ 与 $非严格次小生成树$ 的区别是什么?



活动打卡代码 AcWing 1171. 距离

有猷
17天前
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define re register
#define Re register
#define MAXN 10005
#define MAXM 20005
int n,m,dep[MAXN],val[MAXN],opt[MAXN][20];
int h[MAXN],e[MAXM],v[MAXM],nxt[MAXM],idx;
bool vis[MAXN];
void add(int u,int V,int w){
    e[idx] = V;v[idx] = w;nxt[idx] = h[u];h[u] = idx++;
}
void dfs(int pos){
    for(Re int i = h[pos];i != -1;i = nxt[i]){
        int np = e[i];
        if(vis[np])continue;
        vis[np] = true;
        dep[np] = dep[pos] + 1;
        val[np] = val[pos] + v[i];
        opt[np][0] = pos;
        for(re int i = 1;i <= 14;i++){
            opt[np][i] = opt[opt[np][i - 1]][i - 1];
        }
        dfs(np);
    }
}
int lca(int x,int y){
    if(dep[x] < dep[y])swap(x,y);
    for(re int i = 14;i >= 0;i--){
        if(dep[opt[x][i]] >= dep[y])x = opt[x][i];
    }
    if(x == y)return x;
    for(Re int i = 14;i >= 0;i--){
        if(opt[x][i] != opt[y][i]){
            x = opt[x][i];
            y = opt[y][i];
        }
    }
    return opt[x][0];
}
int main() {
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(Re int i = 1;i < n;i++){
        int x,y,k;
        scanf("%d%d%d",&x,&y,&k);
        add(x,y,k);
        add(y,x,k);
    }
    dep[1] = 1;
    vis[1] = true;
    dfs(1);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int ans = lca(x,y);
        printf("%d\n",val[x] - 2 * val[ans] + val[y]);
    }
    return 0;
}


活动打卡代码 AcWing 1172. 祖孙询问

有猷
18天前
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define re register
#define Re register
#define MAXN 40005
#define MAXM (MAXN * 2)
int n,m,root,dep[MAXN],opt[MAXN][20];//LCA
int h[MAXN],e[MAXM],nxt[MAXM],idx;//graph
int q[MAXN],hh,tt;//queue
void add(int u,int v){
    e[idx] = v;nxt[idx] = h[u];h[u] = idx++;
}
void bfs(){
    memset(dep,0x3f,sizeof dep);
    dep[0] = 0;
    dep[root] = 1;
    q[0] = root;
    while(hh <= tt){
        int pos = q[hh++];
        for(re int i = h[pos];i != -1;i = nxt[i]){
            int np = e[i];
            if(dep[np] <= dep[pos])continue;
            dep[np] = dep[pos] + 1;
            opt[np][0] = pos;
            for(re int j = 1;j <= 15;j++){
                opt[np][j] = opt[opt[np][j - 1]][j - 1];
            }
            q[++tt] = np;
        }
    }
}
int LCA(int x,int y){
    if(dep[x] < dep[y])swap(x,y);
    for(re int i = 15;i >= 0;i--){
        if(dep[opt[x][i]] >= dep[y])x = opt[x][i];
    }
    // cout << x << ' ' << y << endl;
    if(x == y)return x;
    for(re int i = 15;i >= 0;i--){
        if(opt[x][i] != opt[y][i]){
            x = opt[x][i];
            y = opt[y][i];
        }
    }
    return opt[x][0];
}
int main() {
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    for(re int i = 1;i <= n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(v == -1){
            root = u;
            continue;
        }
        add(u,v);
        add(v,u);
    }
    bfs();
    scanf("%d",&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        int ans = LCA(x,y);
        if(ans == x)puts("1");
        else if(ans == y)puts("2");
        else puts("0");
    }
    return 0;
}


活动打卡代码 AcWing 1142. 繁忙的都市

有猷
20天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define re register
#define Re register
#define MAXN 305
#define MAXM 8005
struct node{
    int u,v,w;
}a[MAXM];
bool operator<(node a,node b){
    return a.w < b.w;
}
int n,m,ans,fa[MAXN];
int find(int x){
    if(fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)] = find(y);
}
int main() {
    scanf("%d%d",&n,&m);
    for(re int i = 1;i <= m;i++) {
        scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
    }
    for(re int i = 1;i <= n;i++){
        fa[i] = i;
    }
    sort(a + 1,a + 1 + m);
    int cnt = 0;
    for(re int i = 1;i <= m;i++){
        if(cnt == n - 1)break;
        if(find(a[i].u) != find(a[i].v)){
            ans = a[i].w;
            merge(a[i].u,a[i].v);
            cnt++;
        }
    }
    printf("%d %d\n",cnt,ans);
    return 0;
}


活动打卡代码 AcWing 1141. 局域网

有猷
1个月前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define re register
#define Re register
#define MAXN 205
struct edge{
    int u,v,w;
}a[MAXN];
int n,k,ans,fa[MAXN];
int find(int x){
    if(fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}
void merge(int x,int y){
    x = find(x);y = find(y);
    if(x == y)return;
    fa[y] = x;
}
bool operator<(edge a,edge b){
    return a.w < b.w;
}
int main() {
    cin >> n >> k;
    for(Re int i = 1;i <= n;i++){
        fa[i] = i;
    }
    for(re int i = 1;i <= k;i++){
        cin >> a[i].u >> a[i].v >> a[i].w;
        ans += a[i].w;
    }
    sort(a + 1,a + 1 + k);
    for(re int i = 1;i <= k;i++){
        if(find(a[i].u) == find(a[i].v))continue;
        merge(a[i].u,a[i].v);
        ans -= a[i].w;
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1140. 最短网络

有猷
1个月前

Prim算法与Dijkstra算法的区别:

  • Prim求最小生成树;Dijkstra求最短路
  • Prim用通往该节点的边权更新节点;Dijkstra用通往该节点的边权加所在节点的最短路更新节点
  • Prim结果为各点权值之和;Dijkstra结果为终点权值
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define re register
#define Re register
#define MAXN 105
int n,g[MAXN][MAXN],ans,dis[MAXN];
bool vis[MAXN];
priority_queue<int>q;
void prim(){
    memset(dis,0x3f,sizeof dis);
    dis[1] = 0;
    for(re int i = 1;i <= n;i++){
        int t = 0;
        for(re int j = 1;j <= n;j++){
            if(!vis[j] && (t == 0 || dis[t] > dis[j]))t = j;
        }
        vis[t] = true;
        ans += dis[t];
        for(re int j = 1;j <= n;j++){
            dis[j] = min(dis[j],g[t][j]);
        }
    }
}
int main() {
    cin >> n;
    for(re int i = 1;i <= n;i++){
        for(re int j = 1;j <= n;j++){
            cin >> g[i][j];
        }
    }
    prim();
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 345. 牛站

有猷
1个月前

wjx.png

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define re register
#define Re register
#define MAXN 205
#define INF 0x3f3f3f3f
int n,t,s,e,idx,len,dis[MAXN][MAXN][25],a[MAXN][MAXN],f[MAXN],g[MAXN];
map<int,int>m;
int calc(){
    for(re int p = 1;p <= len;p++){
        for(re int k = 1;k <= idx;k++){
            for(re int i = 1;i <= idx;i++){
                for(re int j = 1;j <= idx;j++){
                    dis[i][j][p] = min(dis[i][j][p],dis[i][k][p - 1] + dis[k][j][p - 1]);
                }
            }
        }
    }
}
void binary(int n,int depth){
    if(n == 0)return;
    bool b = (n & 1);
    if(b){
        memset(f,0x3f,sizeof f);
        for(Re int i = 1;i <= idx;i++){
            for(re int j = 1;j <= idx;j++){
                f[j] = min(f[j],g[i] + dis[i][j][depth]);
            }
        }
        memcpy(g,f,sizeof g);
    }
    binary(n >> 1,depth + 1);
}
int main() {
    scanf("%d%d%d%d",&n,&t,&s,&e);
    len = log2(n);
    m[s] = ++idx;
    if(s != e)m[e] = ++idx;
    memset(dis,0x3f,sizeof dis);
    while(t--){
        int u,v,w;
        scanf("%d%d%d",&w,&u,&v);
        if(!m.count(u))m[u] = ++idx;
        if(!m.count(v))m[v] = ++idx;
        u = m[u];v = m[v];
        dis[u][v][0] = dis[v][u][0] = min(dis[u][v][0],w);
    }
    s = m[s];e = m[e];
    calc();
    memset(g,0x3f,sizeof g);
    g[s] = 0;
    binary(n,0);
    printf("%d\n",f[e]);
    return 0;
}


活动打卡代码 AcWing 344. 观光之旅

有猷
1个月前

Floyd算法执行中dis[i][j]的含义:用前k-1个节点更新的最短路。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define re register
#define Re register
#define INF 0x3f3f3f3f
#define MAXN 105
int n,m,ans = INF,dis[MAXN][MAXN],w[MAXN][MAXN],pos[MAXN][MAXN],st[MAXN * MAXN],idx;
void get_path(int lft,int rgt){
    if(pos[lft][rgt] == 0)return;
    get_path(lft,pos[lft][rgt]);
    st[++idx] = pos[lft][rgt];
    get_path(pos[lft][rgt],rgt);
}
int main() {
    cin >> n >> m;
    memset(dis,0x3f,sizeof dis);
    while(m--){
        int u,v,W;
        scanf("%d%d%d",&u,&v,&W);
        dis[u][v] = W;
        dis[v][u] = W;
        w[u][v] = W;
        w[v][u] = W;
    }
    for(re int k = 1;k <= n;k++){
        for(re int i = 1;i <= n;i++){
            for(re int j = 1;j <= n;j++){
                if(dis[i][j] != INF && w[i][k] != 0 && w[k][j] != 0 && i != j){
                    if(ans > dis[i][j] + w[i][k] + w[k][j]) {
                        ans = dis[i][j] + w[i][k] + w[k][j];
                        idx = 1;st[1] = i;
                        get_path(i,j);
                        st[++idx] = j;
                        st[++idx] = k;
                    }
                }
                if(dis[i][k] + dis[k][j] < dis[i][j]){
                    dis[i][j] = dis[i][k] + dis[k][j];
                    pos[i][j] = k;
                }
            }
        }
    }
    if(ans == INF){
        cout << "No solution." << endl;
        return 0;
    }
    for(re int i = 1;i <= idx;i++) {
        printf("%d ",st[i]);
    }
    printf("\n");
    return 0;
}


活动打卡代码 AcWing 343. 排序

有猷
2个月前
#include<iostream>
#include<cstring>
using namespace std;
#define Re register
#define re register
#define MAXN 35
int n,m,f;
int st[MAXN];
bool dis[MAXN][MAXN];
void floyd() {
    for(re int k = 1;k <= n;k++) {
        for(re int i = 1;i <= n;i++) {
            for(Re int j = 1;j <= n;j++) {
                dis[i][j] |= (dis[i][k] & dis[k][j]);
            }
        }
    }
    for(re int i = 1;i <= n;i++){
        if(dis[i][i])f = 2;
    }
    if(f == 2)return;
    f = 1;
    for(re int i = 1;i <= n;i++){
        for(re int j = 1;j <= n;j++){
            if(!dis[i][j] && i != j && !dis[j][i])f = 0;
        }
    }
}
char get_min() {
    int res = 0;
    for(re int i = 1;i <= n;i++){
        int ok = true;
        for(re int j = 1;j <= n;j++) {
            if(dis[j][i])ok = false;
        }
        res = i;
        if(ok && !st[res])break;
    }
    st[res] = true;
    for(re int i = 1;i <= n;i++){
        dis[res][i] = false;
    }
    return res + 'A' - 1;
}
int main() {
    while(true) {
        cin >> n >> m;
        if(n == 0)return 0;
        int t = 0;
        f = 0;
        memset(dis,0,sizeof dis);
        memset(st,0,sizeof st);
        while(m--){
            char a,b,tmp;
            cin >> a >> tmp >> b;
            if(f == 1 || f == 2)continue;
            a = a - 'A' + 1;
            b = b - 'A' + 1;
            t++;
            dis[a][b] = true;
            floyd();
        }
        // for(re int i = 1;i <= n;i++){
        //     for(re int j = 1;j <= n;j++) {
        //         cout << dis[i][j] << ' ';
        //     }
        //     cout << endl;
        // }
        if(f == 2)printf("Inconsistency found after %d relations.",t);
        else if(f == 0)printf("Sorted sequence cannot be determined.");
        else {
            printf("Sorted sequence determined after %d relations: ",t);
            for(re int i = 1;i <= n;i++) {
                printf("%c",get_min());
            }
            printf(".");
        }
        printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 1125. 牛的旅行

有猷
2个月前
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define re register
#define Re register
#define MAXN 155
#define cmp 0.000001
int n;//normal
double x[MAXN],y[MAXN],dis[MAXN][MAXN];//graph
double res,ans = 1e9 + 7,ans_ = 0;
double dist(int i,int j) {
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
void floyd() {
    for(re int k = 1;k <= n;k++) {
        for(Re int i = 1;i <= n;i++){
            for(re int j = 1;j <= n;j++){
                if(i == j)continue;
                dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
            }
        }
    }
}
int main() {
    cin >> n;
    for(re int i = 1;i <= n;i++) {
        cin >> x[i] >> y[i];
    }
    for(re int i = 1;i <= n;i++) {
        for(re int j = 1;j <= n;j++) {
            char ch;
            cin >> ch;
            if(ch == '1')dis[i][j] = dist(i,j);
            else dis[i][j] = 1e9 + 7;
        }
        dis[i][i] = 0;
    }
    floyd();
    for(re int i = 1;i <= n;i++){
        for(re int j = i + 1;j <= n;j++){
            if(1e9 + 7 - dis[i][j] > cmp){
                ans_ = max(ans_,dis[i][j]);
                continue;
            }
            double a1 = 0,a2 = 0;
            for(re int k = 1;k <= n;k++){
                if(!(1e9 + 7 > dis[i][k]))continue;
                a1 = max(a1,dis[i][k]);
            }
            for(re int k = 1;k <= n;k++){
                if(!(1e9 + 7 > dis[j][k]))continue;
                a2 = max(a2,dis[j][k]);
            }
            ans = min(ans,a1 + a2 + dist(i,j));
        }
    }
    printf("%.6lf\n",max(ans,ans_));
    return 0;
}