头像

Fancy_z




离线:4天前



Fancy_z
1个月前
#include<iostream>
using namespace std;
const int N=100010;
int q[N];
int sizee[N];
int n.m;

int find(int x)
{
    if(q[x]!=x)q[x]=find(q[x]);
    return q[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        q[i]=i;
        sizee[i]=1;
    }

    while(m--)
    {
        char op[5];
        int a,b;
        scanf("%s",op);
        if(op[0]=='C')
        {
            cin>>a>>b;
            if(find(a)==find(b)) continue;
            sizee[find(b)]+=sizee[find(a)];
            q[find(a)]=find(b);
        }
        else if(op[1]=='1')
        {
            cin>>a>>b;
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else 
        {
            cin>>a;
            cout<<sizee[find(a)]<<endl;
        }
    }
    return 0;
}



Fancy_z
1个月前
#include<iostream>
using namespace std;
const int N=100010;
int q[N];
int sizee[N];
int n.m;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        q[i]=i;
        sizee[i]=1;
    }

    while(m--)
    {
        char op[5];
        int a,b;
        scanf("%s",op);
        if(op[0]=='C')
        {
            cin>>a>>b;
            if(find(a)==find(b)) continue;
            sizee[find(b)]+=sizee[find(a)];
            q[find(a)]=find(b);
        }
        else if(op[1]=='1')
        {
            cin>>a>>b;
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else 
        {
            cin>>a;
            cout<<sizee[find(a)]<<endl;
        }
    }
    return 0;
}



Fancy_z
1个月前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
const int INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist,0x3f,sizeof(dist));

    int res=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;
        }

        if(i&&dist[t]==INF) return INF;
        if(i) res+=dist[t];

        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],g[t][j]);
        }
        st[t]=true;
    }
    return res;
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof(g));

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b]+c);
    }

    int t=prim();

    if(t==INF)coust<<"impossible"<<endl;
    else cout<<t<<endl;
    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

Fancy_z
1个月前
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=210;
const int INF=1e9;

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

void Floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;
        }
    }

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);
    }

    Floyd();

    while(Q--)
    {
        int a,b;
        cin>>a>>b;
        if(d[a][b]>INF/2)cout<<"impossible"<<endl;
        else cout<<d[a][b]<<endl;
    }
    return 0;
}



Fancy_z
1个月前

题目描述

Kruskal算法求最小生成树(多用于稀疏图)

(1)将所有边按照权重从小到大排序O(mlogm)
(2)枚举每条边a->b,权重为c

并查集:连通块中点的数量
O(m)
   if a->b不连通
    将这条边加入集合中,即将a,b连起来

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1000100;

int n,m;
int p[N];

struct Edge
{
    int a,b,w;

    bool operator< (const Edge &W) const   //重载<
    {
        return w<W.w;
    }
}edge[N];


int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;

    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edge[i]={a,b,w};
    }

    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);   //分别找到a,b的祖宗节点

        if(a!=b)   //如果祖宗节点不一样,则a,b不连通
        {
            p[a]=b;   //将两个点所在的集合合并
            res+=w;      
            cnt++;
        }
    }
    if(cnt<n-1) cout<<"impossible"<<endl;  //如果总的边数小于,则不连通
    else cout<<res<<endl;   //输出所有边的长度之和

    return 0;
}



Fancy_z
1个月前

题目描述

Prim算法求最小生成树(边的正负无关)

朴素版算法:类似于Dijstra算法
(每次先找到t,(不在集合中,且距离最小的点),找到之后用经过t的路径长度来更新距离,然后把t加入集合中,集合中是已经确定了最短路的点

第一次在n个点中选,第二次在n-1个点中选。。。)

初始化距离为 正无穷,然后n次迭代
第一次是随便找点,因为都是正无穷,接下来找的点是与上一个点距离最小的点

每次都要在n个点中选

for(i=0;i<n;i++)
{
    (1)找到不在集合当中的距离最小的点(集合中为在当前连通块中的所有点)
    (2)用t更新其他点到集合的距离:这个点连向集合中的其他边,在这些边中找到距离最小的边
    (3)把t加到集合当中(st[t]=true)
}

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist,0x3f,sizeof dist);

    int res=0;  //最小生成树中所有边的长度之和
    for(int i=0;i<n;i++)   //n次迭代
    {
        int t=-1;
        for(int j=1;j<=n;j++)   //找到集合外最小距离的点
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
            t=j;
        }

        if(i&&dist[t]==INF) return INF;  //如果不是第一个点,当前最近的点到该点的距离是正无穷,即不连通
        if(i) res+=dist[t];  //只要不是第一条边,,

        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],g[t][j]);   //先累加再更新,更新其他点到集合的距离,不是起点到其他点的距离。防止自环权重为负的情况
        }

        st[t]=true;
    }
    return res;
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);   //初始化为正无穷

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);   //没有重边
    }

    int t=prim();

    if(t==INF)cout<<"impossible"<<endl;//所有点不连通则没有生成树
    else
    cout<<t<<endl;
    return 0;
}



Fancy_z
1个月前

题目描述

Floyd求最短路(多元最短路)
基于动态规划:
(三维)d[k,i,j]:从i出发,只经过1~k这些中间点到达j的最短距离

邻接矩阵存储图
d[i][j]存所有的边

d[k,i,j]=d[k-1,i,k]+d[k-1,k,j]
d[i,j]=d[i,k]+d[k,j]

for(k=1;k<=n;k++)  
{
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        }
    }
}

d[i][j]存i到j的最短路长度

C++ 代码

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

const int N=210,INF=1e9;

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

void Floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}
int main()
{
    cin>>n>>m>>Q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)d[i][j]=0;   //所有d[i][i]初始化为0,去掉自环(边都大于0)
            else d[i][j]=INF;   //其他的边都是正无穷
        }
    }
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);    //在重边中找到最小的边
    }

    Floyd();

    while(Q--)
    {
        int a,b;
        cin>>a>>b;
        if(d[a][b]>INF/2)cout<<"impossible"<<endl;   //判断不存在通路
        else cout<<d[a][b]<<endl;
    }
    return 0;

}



Fancy_z
1个月前

题目描述

堆优化
(1)手写堆:时刻保证堆中有n个数
(2)优先队列:每次修改都往堆中插入一个数,可能有m个数(O(mlogm))可能会有冗余数据,所以要加判断

稀疏图:用邻接表(不需要考虑重边)

for i:1~n 迭代n次,更新n次,则时间复杂度为O(n^2)
{
   t(找到不在s中的距离最近的点)   O(1)n次

   将点t加入到s中  (n次)

   t来更新所有点的距离(从t出来的所有的边能不能更新所有点的距离)(t到起点的距离能否更新当前点到起点(1号点的)直接的距离)即:判断dist[x]>dist[t]+w  (m次,m为该点边的数量)修改:mlogn
}

C++ 代码

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

typedef pair<int,int> PII;
const int N=150010;

int n,m;
int h[N],w[N],e[N],ne[N],idx;   //堆存储
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b;   //存储点的编号
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dijstra()
{
    memset(dist,0x3f,sizeof(dist));

    dist[1]=0;

    priority_queue<PII,vector<PII>,greater<PII>> heap;    //只有m个数(m条边)

    heap.push({0,1});   //放入1号点,距离是0,编号是1

    while(heap.size())
    {
        auto t=heap.top();   //找到当前距离最短的点
        heap.pop();

        int ver=t.second;  //ver表示编号
        int distance=t.first;   //表示距离

        if(st[ver]) continue;   //如果这个点之前已经找过,则跳过这个点

        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])  //执行总数为m
        {
            int j=e[i];  //存储编号
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});   //更新的新点
            }
        }

    }
    if(dist[n]==0x3f3f3f3f)return -1;   // memset是按字节赋值,一个int是32位4字节,所以有四个3f
    return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    int t=dijstra();

    cout<<t<<endl;

    return 0;
}



Fancy_z
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],w[N],idx;
int dist[N];   //每个点到1号点的距离
bool st[N];  //每个点的最短路是否被确定了

typedef pair<int,int> PII;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
int dijstra()
{
    memset(dist,0x3f,sizeof(dist));

    dist[1]=0;               //第一步

    priority_queue<PII,vector<PII>,greater<PII>>heap;

    heap.push({0,1});

    while(heap.size())
    {
        auto t=heap.top();  //当前距离最小的点
        heap.pop();

        int ver=t.second;
        int distance=t.first;

        if(st[ver]) continue;

        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];  //存储编号
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;    //如果到1的距离为正无穷,则表明是不连通的
    return dist[n];  //否则返回距离
}
int main()
{
    cin>>n>>m;
   memset(g,0x3f,sizeof g);

   while(m--)
   {
       int a,b,c;
       cin>>a>>b>>c;
      add(a,b,c);
   }

   int t=dijstra();
   cout<<t<<endl;
   return 0;
}



Fancy_z
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int dijstra()
{
    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;

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

    if(st[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);

    }
    int t=dijstra();
    cout<<t<<endl;
    return 0;
    }
}