2022.2.16

news/2024/7/15 17:35:11 标签: 算法, 动态规划, 图论

重新看了下最小生成树

kruskal算法

【1】先将图中带权的(两点)全部得到(放在结构体中)

【2】然后按权值大小排序(从小到大)

【3】将点与点连成边(用并查集判断是否有环)

最小生成树(模板题)

思路:和上面一样

#include<bits/stdc++.h>
using namespace std;
struct edge
{
    int x;
    int y;
    int z;
} edge[200010];
int father[5010];
int n,m;
void fastsort(int left,int right)
{
    int i=left,j=right;
    int mid=edge[(left+right)/2].z;
    if(left>=right)
        return;
    while(i<=j)
    {
        while(edge[j].z>mid)
            j--;
        while(edge[i].z<mid)
            i++;
        if(i<=j)
        {
            struct edge temp=edge[i];
            edge[i]=edge[j];
            edge[j]=temp;
            j--;
            i++;
        }
    }
    fastsort(left,j);
    fastsort(i,right);
}

//找祖宗
int find_root(int x)
{
    if(x!=father[x])
        father[x]=find_root(father[x]);
    return father[x];
}

int main()
{
    int ans=0;
    long long sum=0;
    cin>>n>>m;
    //将边输入
    for(int i=1; i<=m; i++)
    {
        cin>>edge[i].x>>edge[i].y>>edge[i].z;
    }
    fastsort(1,m);
//    for(int i=1;i<=m;i++)
//        cout<<edge[i].x<<' '<<edge[i].y<<' '<<edge[i].z<<endl;
    //并查集
    for(int i=1; i<=n; i++)
        father[i]=i;
    for(int i=1; i<=m; i++)
    {
        int x_root=find_root(edge[i].x);
        int y_root=find_root(edge[i].y);
        if(x_root!=y_root)
        {
            sum+=edge[i].z;
            father[x_root]=y_root;
            ans++;
            if(ans==n-1)
                break;
        }
    }
//    for(int i=1;i<=m;i++)
//        if(father[i]==i)
//            ans++;
//    if(ans>1)
    if(ans!=n-1)
        cout<<"orz"<<endl;
    else
        cout<<sum<<endl;
    return 0;
}

拆地毯

思路:和上面唯一不同的是这里要求最大值,所以是从大到小排列

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct edge
{
    int u,v,w;
}edge[100005];
int father[100005];
void fastsort(int left,int right)
{
    int i=left,j=right;
    int mid=edge[(left+right)/2].w;
    if(left>=right)
        return;
    while(i<=j)
    {
        while(edge[j].w<mid)
            j--;
        while(edge[i].w>mid)
            i++;
        if(i<=j)
        {
            struct edge temp=edge[i];
            edge[i]=edge[j];
            edge[j]=temp;
            j--;
            i++;
        }
    }
    fastsort(left,j);
    fastsort(i,right);
}
int find_root(int x)
{
    if(father[x]!=x)
        father[x]=find_root(father[x]);
    return father[x];
}
int main()
{
    int ans=0,sum=0,Max=0;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    }
    //从大到小排序
    fastsort(1,m);
    for(int i=1;i<=n;i++)
        father[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u_root=find_root(edge[i].u);
        int v_root=find_root(edge[i].v);
        if(u_root!=v_root)
        {
            sum+=edge[i].w;
            father[u_root]=v_root;
            ans++;
            if(ans==k)
                break;
        }
    }
    cout<<sum<<endl;
    return 0;
}



口袋的天空

思路:和模板又一样了

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int father[10005];
struct spun
{
    int x,y,l;
}candy[10005];
void fastsort(int left,int right)
{
    int i=left,j=right;
    int mid=candy[(left+right)/2].l;
    if(left>=right)
        return ;
    while(i<=j)
    {
        while(candy[j].l>mid)
            j--;
        while(candy[i].l<mid)
            i++;
        if(i<=j)
        {
            struct spun temp=candy[i];
            candy[i]=candy[j];
            candy[j]=temp;
            j--;
            i++;
        }
    }
    fastsort(left,j);
    fastsort(i,right);
}
int find_root(int x)
{
    if(father[x]!=x)
        father[x]=find_root(father[x]);
    return father[x];
}
int main()
{
    int ans=0,sum=0;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>candy[i].x>>candy[i].y>>candy[i].l;
    }
    fastsort(1,m);
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int x_root=find_root(candy[i].x);
        int y_root=find_root(candy[i].y);
        if(x_root!=y_root)
        {
            sum+=candy[i].l;
            father[x_root]=y_root;
            ans++;
            if(ans==n-k)
                break;
        }
    }
    if(ans==n-k)
        cout<<sum<<endl;
    else
        cout<<"No Answer"<<endl;
    return 0;
}

无线通讯网

思路:这个题和前面题的不同在于这个题他的权值需要自己求

题目中给出了点的坐标,我们只要将两点之间的距离(距离公式)求出来,就又是模板题了

注意:数组要开大一点,要注意 double 型的使用是在哪些地方

#include<bits/stdc++.h>
using namespace std;
int s,p,cnt;
int father[501];
//坐标
struct coordinete
{
    int x,y;
}coordinate[501];

struct edge
{
    int u,v;
    //注意这个double
    double w;
}edge[400005];

//注意这里的w是double
void add(int u,int v,double w)
{
    cnt++;
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
}
void fastsort(int left,int right)
{
    int i=left,j=right;
    double mid=edge[(left+right)/2].w;
    if(left>=right)
        return ;
    while(i<=j)
    {
        while(edge[j].w>mid)
            j--;
        while(edge[i].w<mid)
            i++;
        if(i<=j)
        {
            struct edge temp=edge[i];
            edge[i]=edge[j];
            edge[j]=temp;
            j--;
            i++;
        }
    }
    fastsort(left,j);
    fastsort(i,right);
}
int find_root(int x)
{
    if(father[x]!=x)
        father[x]=find_root(father[x]);
    return father[x];
}
int main()
{
    int ans=0;
    double sum=0;
    cin>>s>>p;
    for(int i=1;i<=p;i++)
    {
        cin>>coordinate[i].x>>coordinate[i].y;
    }
    for(int i=1;i<=p;i++)
    {
        for(int j=i+1;j<=p;j++)
        {
            //double
            double w=sqrt((coordinate[i].x-coordinate[j].x)*(coordinate[i].x-coordinate[j].x)+(coordinate[i].y-coordinate[j].y)*(coordinate[i].y-coordinate[j].y));
            add(i,j,w);
        }
    }
    fastsort(1,cnt);
    for(int i=1;i<=p;i++)
        father[i]=i;
    for(int i=1;i<=cnt;i++)
    {
        int u_root=find_root(edge[i].u);
        int v_root=find_root(edge[i].v);
        if(u_root!=v_root)
        {
            //注意这里不是把这个加上去而是让它等于到那里的最大值
            sum=edge[i].w;
            father[u_root]=v_root;
            ans++;
            if(ans==p-s)
                break;
        }
    }
    printf("%.2lf\n",sum);
    return 0;
}

P2872 Building Roads s

思路:和无线通讯网挺像的,就都是double型,还都需要求权值

            但是这个题中输入的m条边是相对于后面连接好的(这里可用并查集表示连好,也可以用权值为0表示)

就离谱:这个题用sort能过,自己写的fastsort过不了(可能是还是比sort慢了,嘤嘤嘤)

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int father[1001];
struct coordinate
{
    int x,y;
}c[1001];
struct edge
{
    int u,v;
    double w;
}edge[5000001];
void add(int u,int v,double w)
{
    cnt++;
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
}
bool cmp(struct edge a,struct edge b)
{
    return a.w<b.w;
}
int find_root(int x)
{
    if(father[x]!=x)
        father[x]=find_root(father[x]);
    return father[x];
}
int main()
{
    int ans=0;
    double sum=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i].x>>c[i].y;
        father[i]=i;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            double w=sqrt((double)(c[i].x-c[j].x)*(c[i].x-c[j].x)+(double)(c[i].y-c[j].y)*(c[i].y-c[j].y));
            add(i,j,w);
        }
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        int uroot=find_root(u);
        int vroot=find_root(v);
        father[uroot]=vroot;
    }
    sort(edge+1,edge+1+cnt,cmp);
    for(int i=1;i<=cnt;i++)
    {
        int uroot=find_root(edge[i].u);
        int vroot=find_root(edge[i].v);
        if(uroot!=vroot)
        {
            sum+=edge[i].w;
            father[uroot]=vroot;
            ans++;
            //n个点即共有n-1条边,但其中的m条已经连接好了
            if(ans==n-1-m)
                break;
        }
    }
    printf("%.2lf\n",sum);
    return 0;
}

自己写的过不了的快排:(TLE)

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int father[1001];
struct coordinate
{
    int x,y;
} c[1001];
struct edge
{
    int u,v;
    double w;
} edge[1000001];
int find_root(int x)
{
    if(x==father[x])
    {
        return x;
    }
    return father[x]=find_root(father[x]);
}
void fastsort(int left,int right)
{
    int i=left,j=right;
    int mid=edge[(left+right)/2].w;
    if(left>=right)
        return;
    while(i<=j)
    {
        while(edge[j].w>mid)
            j--;
        while(edge[i].w<mid)
            i++;
        if(i<=j)
        {
            struct edge temp=edge[i];
            edge[i]=edge[j];
            edge[j]=temp;
            j--;
            i++;
        }
    }
    fastsort(left,j);
    fastsort(i,right);
}
int main()
{
    int ans=0;
    double sum=0;
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d %d",&c[i].x,&c[i].y);
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            cnt++;
            edge[cnt].u=i;
            edge[cnt].v=j;
            edge[cnt].w=sqrt((double)(c[i].x-c[j].x)*(c[i].x-c[j].x)+(double)(c[i].y-c[j].y)*(c[i].y-c[j].y));
        }
    }
    fastsort(1,cnt);
    //sort(edge+1,edge+1+cnt,cmp);
    for(int i=1; i<=n; i++)
    {
        father[i]=i;
    }
    for(int i=1; i<=m; i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        father[find_root(u)]=find_root(v);
    }
    for(int i=1; i<=cnt; i++)
    {
        int uroot=find_root(edge[i].u);
        int vroot=find_root(edge[i].v);
        if(uroot!=vroot)
        {
            father[uroot]=vroot;
            sum+=edge[i].w;
            ans++;
            if(ans==n-1-m)
                break;
        }
    }
    printf("%.2lf\n",sum);

}

 

这些题全用kruskal做了,额。


http://www.niftyadmin.cn/n/921755.html

相关文章

已知一点求最近点(问题请教)

问题的提出&#xff1a;已知点P(经纬度),查找该点最临近的点D(点,线,面),返回D的名称及与P的方向,位置和距离关系,地物总数大于50万个问题的问题&#xff1a;一&#xff1a;是否基于控件&#xff1f;基于控件和非基于控件应该怎么做&#xff1f;二&#xff1a;坐标系统是什么系…

uboot 如何设置网关地址_干货分享,FBM发货退货地址如何设置?

很多卖家一般都有FBA和FBM两种渠道发货&#xff0c;但都会遇到同样的问题&#xff0c;那就是买家对商品不满意要求退货。由于FBA都是由亚马逊物流直接负责&#xff0c;所以该种渠道的买家退货都是退回亚马逊仓库了&#xff0c;无需卖家负责。但FBM是由卖家自己发货&#xff0c;…

2006年德国世界杯(第10天)——世界杯,想说爱你不容易!

不知不觉中&#xff0c;世界杯陪我们度过了10个激情四射的夜晚。心理的满足和身体的疲劳都到达了一个极限。虽然是周日&#xff0c;还要迎接新的一周的工作。但仍不舍放弃巴西队的比赛。本来自己的习惯是正常的工作日&#xff0c;看第2场的半场球到一点&#xff0c;但今晚自己打…

2022.2.17

prim算法&#xff1a;和Dijkstra算法的实现有些类似 【1】从起点开始往后找和这个点连接的权值最小的点&#xff0c;连到树上 【2】重复第一步 例题&#xff1a; 最小生成树&#xff1a; #include<bits/stdc.h> using namespace std; #define inf 0x3f3f3f3f int Map…

css 百分比 怎么固定正方形_CSS题目系列(2) - 实现一个固定比例盒子

描述在开发过程中&#xff0c;会有这么一个情况&#xff0c;需要将一个盒子的尺寸定义为固定比例&#xff0c;且尺寸需根据视图的尺寸来进行缩放&#xff0c;也就是响应式&#xff0c;常见的多如有矩形、圆形等。下面我将使用下面的例子为大家进行讲解&#xff1a;正文其实实现…

openSource 知:回合开源社区补丁

文章目录1. 前言2. 回合2.1. 举例2.2. 关键补丁2.3. 前置补丁2.3.1. 直接前置补丁2.3.2. 间接前置补丁2.4. 后置补丁2.5. 补丁拓扑2.6. 漏合2.6.1. 漏合的影响2.6.2. 防漏合措施2.6.3. 漏合的分类2.7. 工具2.7.1. 生成补丁2.7.2. 分组补丁3. 后语1. 前言 我们在使用开源软件的…