2022.2.13

上午：

看书；

看网课；

炸铁路；

（一看到题目就想到前面学的并查集）但是没做出来

下午：

学长讲课；

Dijkstra算法（重点）

模板：

#include
using namespace std;
const int N=105;
const int inf=1e9+5;
int n,m,s,e;
int mp[N][N];
//当前距离数组
int low[N];
int vis[N];
//初始化
void init()
{
    for(int i=1; i<=n; i++)
    {
        low[i]=inf;
        vis[i]=0;
    }
}
int dij()
{
    low[s]=0;
    //看下起点可以到哪些点
    for(int i=1; i<=n; i++)
    {
        low[i]=mp[s][i];
    }
    low[s]=0;
    vis[s]=1;

    for(int i=1;i<=n;i++)
    {
        //这个找到最短距离的点是哪个点
        int idx=-1,Min=inf;
        //哪些点可以当起点
        for(int j=1; j>n>>m>>s>>e;
    //然所有的边不能走
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            mp[i][j]=inf;
        }
    }
    for(int i=1; i<=m; i++)
    {
        int a,b,v;
        cin>>a>>b>>v;
        mp[a][b]=v;
        mp[b][a]=v;
    }
    init();
    dij();
}

晚上：

继续炸铁路；

用并查集做出来了

思路：

【1】用结构体将一条铁路装起来（即，装两个城市）

【2】输入铁路的边后，给边排序（按city[i].a的大小排序）

【3】列举各条铁路发生爆炸后的情况，找到无相连点的城市装进表示最终结果的result[]里面

【4】注意，可能有result[i].a==result[j].a的情况出现，就在最后输出答案之前再排一次序

#include
//用一个结构体来装这条铁路的两个城市
struct node
{
    int a;
    int b;
} city[50001],result[50001];
int n,m;
int father[151];
void fastsort(int left,int right)
{
    int i=left,j=right;
    int mid=city[(left+right)/2].a;
    if(left>=right)
        return ;
    while(i<=j)
    {
        while(city[j].a>mid)
            j--;
        while(city[i].acity[i].b)
        {
            int temp=city[i].a;
            city[i].a=city[i].b;
            city[i].b=temp;
        }
    }
    fastsort(1,m);
    int num=1;
    for(int i=1; i<=m; i++)
    {
        for(int j=1; j<=n; j++)
            father[j]=j;
        for(int j=1; j<=m; j++)
        {
            if(i!=j)
                combine(city[j].a,city[j].b);
        }
        for(int j=2; j<=n; j++)
        {
            if(find_root(father[j])!=find_root(father[j-1]))
            {
                result[num].a=city[i].a;
                result[num].b=city[i].b;
                num++;
                break;
            }
        }
    }
    for(int i=1;iresult[j].b)
                {
                    struct node temp=result[i];
                    result[i]=result[j];
                    result[j]=temp;
                }
            }
        }
    }
    for(int i=1; i