xp04 - day05

userId_undefined
HCecbje
金牌教练

2025-08-16 17:18:20

发布于：浙江

213阅读
0回复
0点赞

找社团老大 垃圾并查集

#include<bits/stdc++.h>
using namespace std;
int p[200010];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i] = i;//认自己为老大
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            int t = p[x];//x的最大老大
            while(t!=p[t])t = p[t];
            int k = p[y];//y的最大老大
            while(k!=p[k])k = p[k];
            p[k] = t;
        }else{
            int k = p[y];//y的最大老大
            while(k!=p[k]){
                k = p[k];
            }
            int t = p[x];//x的最大老大
            while(t!=p[t]){
                t = p[t];
            }
            if(k==t)cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }
    return 0;
}

并查集 路径压缩

#include<bits/stdc++.h>
using namespace std;
int p[200010];
//路径压缩   变成菊花树
// 时间复杂度 O(4*n)
int findboss(int x){
    if(x!=p[x])p[x] = findboss(p[x]);
    return p[x];
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i] = i;//认自己为老大
    while(m--){
        int op,x,y;
        cin>>op>>x>>y;
        int bossx = findboss(x);
        int bossy = findboss(y);
        if(op==1){
            //找到x和y的最终boss
            p[bossx] = bossy;
        }else{
            if(bossx!=bossy)cout<<"N"<<endl;
            else cout<<"Y"<<endl;
        }
    }
    return 0;
}

// kruskal   mlogm
#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,w;
}a[200010];
bool cmp(node x,node y){
    return x.w<y.w;
}
int p[100010];
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].w;
    sort(a+1,a+m+1,cmp);
    long long ans = 0;//最小生成树权重总和
    int cnt = n;// n个连通块
    for(int i=1;i<=m;i++){
        int x = a[i].x,y = a[i].y,w = a[i].w;
        int px = find(x),py = find(y);
        if(px!=py){
            p[px] = py;
            ans+=w;
            cnt--;//连通块数量-1
        }
    }
    if(cnt==1)cout<<ans;
    else cout<<"orz";
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[1010];
struct node{
    int x,y,c;
}a[100010];
bool cmp(node x,node y){
    return x.c<y.c;
}
int find(int x){
    if(p[x]!=x)p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i] = i;
    for(int i=1;i<=m;i++){
        cin>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+1+m,cmp);
    int cnt = n;
    for(int i=1;i<=m;i++){
        int pa = find(a[i].x),pb = find(a[i].y);
        if(pa!=pb){
            p[pa] = pb;
            cnt--;
        }
        if(cnt==1){
            cout<<a[i].c;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

团伙 (n^2)

#include<bits/stdc++.h>
using namespace std;
bool g[1010][1010];// g[i][j]=1  i和j为敌人
int p[1010];
int find(int x){
    if(p[x]!=x)p[x] = find(p[x]);
    return p[x];
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    while(m--){
        char op;
        int x,y;
        cin>>op>>x>>y;
        if(op=='E'){
            g[x][y]=g[y][x]=1;
            for(int i=1;i<=n;i++){
                if(g[x][i]){
                    int pi = find(i),py = find(y);
                    p[pi] = py;
                }
                if(g[y][i]){
                    int pi = find(i),px = find(x);
                    p[pi] = px;
                }
            }
        }else{
            int px = find(x),py = find(y);
            p[px] = py;
        }
    }
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(find(i)==i)cnt++;//判断是不是老大
    }
    cout<<cnt;
    return 0;
}

扩展域并查集

#include<bits/stdc++.h>
using namespace std;
bool g[1010][1010];// g[i][j]=1  i和j为敌人
int p[2010];//朋友
int find(int x){
    if(p[x]!=x)p[x] = find(p[x]);
    return p[x];
}
int main(){
    int n,m;
    cin>>n>>m;
    // 1-n 表示 朋友   n+1  - 2n 敌人
    for(int i=1;i<=2*n;i++)p[i] = i;
    while(m--){
        char op;
        int x,y;
        cin>>op>>x>>y;
        if(op=='F'){
            p[find(x)] = find(y);
        }else{
            p[find(x+n)] = find(y);
            p[find(y+n)] = find(x);
        }
    }
    int cnt = 0;
    for(int i=1;i<=n;i++)if(find(i)==i)cnt++;
    cout<<cnt;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
char g[2010][2010];
int d[2010][2010];
int dx[] = {1,-1,-1,1};
int dy[] = {1,-1,1,-1};
int n,m,sx,sy,ex,ey;
struct node{
    int x,y;
};
int main(){
    cin>>n>>sx>>sy>>ex>>ey;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>g[i][j];
            d[i][j] = -1;
        }
    }
    queue<node> q;
    d[sx][sy] = 0;//起点
    q.push({sx,sy});
    while(q.size()){
        node u = q.front();
        q.pop();
        int x = u.x,y = u.y;
        for(int i=0;i<4;i++){
            for(int k=1;;k++){
                int nx = x + dx[i] * k;
                int ny = y + dy[i] * k;
                if(nx<1 || nx>n || ny<1 || ny>n)break;
                if(g[nx][ny]=='#')break;
                if(d[nx][ny]!=-1)break;
                if(d[nx][ny]==-1){
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx,ny});
                }
            }
        }
    }
    cout<<d[ex][ey];
    return 0;
}

dijskra 朴素版

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010; 
int n, m, s;
int dist[N];         // dist[i]：源点到 i 的最短距离
bool state[N];       // state[i]：是否已经确定最短路径
vector<pair<int,int>> g[N]; // 邻接表存图，{邻点，边权}
void Dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0; // 源点到自身为 0
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!state[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        state[t] = true;
        for (auto [v, w] : g[t]) { 
            dist[v] = min(dist[v], dist[t] + w);
        }
    }
}
int main() {
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
    }
    Dijkstra();
    for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
}

dijksra 堆优化版本

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
struct Node {
    int id;
    int dist;
    bool operator<(const Node& other) const {
        return dist > other.dist;
    }
};
vector<pair<int, int>> tr[N];
int n, m,s;
int dist[N];
bool vis[N];
int main() {
    cin >> n >> m >> s;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        tr[a].push_back({b, c});
    }
    for (int i = 1; i <= n; i++) dist[i] = 1e9;
    priority_queue<Node> q;
    dist[s] = 0;
    q.push({s, 0});
    while (!q.empty()) {
        Node u = q.top();
        q.pop();
        if (vis[u.id]) continue;
        vis[u.id] = true;
        for (auto x : tr[u.id]) {
            int v = x.first;
            int w = x.second;
            if (dist[v] > dist[u.id] + w) {
                dist[v] = dist[u.id] + w;
                q.push({v, dist[v]});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dist[i] == 1e9) cout << -1 << " ";
        else cout << dist[i] << " ";
    }
    return 0;
}

判断负环 bellman-Ford

// 判断负环  bellman-Ford
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 10010;
struct Edge {
    int u, v, w;
} edges[M];
int n, m, s;
int d[N];
int last[N];
bool bellman_ford() {
    for (int i = 1; i <= n; i++) d[i] = 1e9;
    d[s] = 0;
    for (int i = 1; i <= n - 1; i++) {
        bool flag = true;
        for(int j=1;j<=n;j++)last[j] = d[j];
        for (int j = 0; j < m; j++) {
            Edge e = edges[j];
            if (d[e.u] < 1e9 && d[e.v] > last[e.u] + e.w) {
                flag=false;
                d[e.v] = last[e.u] + e.w;
            }
        }
        if(flag)break;
    }
    // 再尝试一次松弛，检测负环
    for (int j = 0; j < m; j++) {
        auto e = edges[j];
        if (d[e.u] < 1e9 && d[e.v] > d[e.u] + e.w) {
            return false; // 负环
        }
    }
    return true; // 没有负环
}
int main() {
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }
    if (!bellman_ford())  cout << "no solution" << endl;
    else {
        for (int i = 1; i <= n; i++) {
            if (d[i] == 1e9) cout << -1 << " ";
            else cout << d[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

spfa 最坏 O(nm)

//spfa 最坏 nm

#include<bits/stdc++.h>
using namespace std;
struct node{
	int y,w;
};
int d[1010];//距离
bool vis[1010];//标记
int cnt[1010];
vector<node> g[1010];
int main(){
	int n,m,s;
	cin>>n>>m>>s;
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});//有向图
    }
    for(int i=1;i<=n;i++)d[i]=1e9;//无穷大
    queue<int> q;
    q.push(s);
    d[s] = 0;//初始化路径
    vis[s] = 1;
    while(q.size()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i=0;i<g[u].size();i++){
            node now = g[u][i];
            int ne = now.y,w = now.w;
            if(d[ne]>d[u]+w){
                d[ne] = d[u]+w;
                cnt[ne] = cnt[u] + 1;//更新操作需要累加
                if(cnt[ne]>=n){
                    cout<<"no solution";
                    return 0;
                }
                if(!vis[ne]){
                    vis[ne]=1;
                    q.push(ne);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(d[i]==1e9)cout<<-1<<" ";
        else cout<<d[i]<<" ";
    }
    return 0;
}

Floyd

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n,m;
long long f[N][N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			f[i][j] = 1e9;
	for(int i=1;i<=m;i++){
		long long u,v,w;
		cin>>u>>v>>w;
		f[u][v] = min(f[u][v],w);
	}
	for(int i=1;i<=n;i++)f[i][i] = 0;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
                if(f[i][k]==1e9 || f[k][j]==1e9)continue;
				f[i][j] = min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(f[i][i]<0){
			cout<<-1;
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<f[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}
userId_undefined
去预览
0/2000

全部评论 7

  • userId_undefined
    Stars_Seeker
    题解仙人USACO出题人

    %%%

    2025-08-16 来自 重庆

    1
  • userId_undefined
    LP
    倔强青铜出道萌新

    沙发，有帮助，赞亿个

    2025-08-16 来自 浙江

    1
  • userId_undefined
    1145141919810
    时间刺客时空双修者空间掌握者BUG超度大师秩序白银

    沙发，有帮助，赞亿个\color{#ff1111}\text{沙}\color{#f0281c}\text{发}\color{#e13f27}\text{，}\color{#d25632}\text{有}\color{#c36d3d}\text{帮}\color{#b48448}\text{助}\color{#a59b53}\text{，}\color{#96b25e}\text{赞}\color{#87c969}\text{亿}\color{#78e074}\text{个}

    2025-08-16 来自 浙江

    1
  • userId_undefined
    宋雨琦的狗
    时空双修者荣耀黄金

    %%%orz

    2025-08-16 来自 浙江

    0
  • userId_undefined
    杨熙铭
    出道萌新时间刺客空间掌握者时空双修者字符串·魔法使贪心·贪心尝试者

    学车吗

    2025-08-16 来自 浙江

    0
  • userId_undefined
    不向外出售
    时间刺客空间掌握者时空双修者倔强青铜出道萌新

    买挖机配件吗

    2025-08-16 来自 浙江

    0
  • userId_undefined
    ༺ཌEnder☠Dragonད༻
    I/O·IO入门者数组·数组操作员

    沙发，有帮助，赞亿个⭐⭐⭐⭐⭐

    2025-08-16 来自 浙江

    0

热门讨论