xp04 - day05
2025-08-16 17:18:20
发布于：浙江
197阅读
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;
}
有帮助，赞一个