ICPC入门尝试周总结篇（七）

这一周主要学习了图论的知识，主要学习了并查集和拓补排序，目前为止，更善于应用并查集，对并查集接触的更多一点，理解的也更多一点。

目前为止解了几个题，千篇一律给我的感觉就是套路，给数组默认一个代表元素，不在同一个集合里就union，找根，查看两个结点是否相同就是分别查找根，如果根相同就是联通的，否则就是不连通，图论的过程中也涉及到一些搜索问题。

目前做的有让我绊住脚的就是这个营救的题目：营救 - 洛谷

（当然还有其他题，好几个。。。）

这个题我一开始思路并没太有，只知道这是用并查集做的，但看了题解好像并没有直接用最近学的并查集做的，就一时陷入了迷茫，但是后来就想并查集就是那个模板，先搬上去再说，万一写着写着就会了呢？事实上就是写着写着就会了，从s至t，拥挤度最大值最小，我首先让道路之间按拥挤度做了排序，这样查询到这条路线能行得通的话就是拥挤度最小的了，但最后发现我陷入了一个误区，就是我后来我判断的时候写成了这样：

if(p[i].v==t&&find(p[i].u)==s)

{

cout << p[i].w;

break;

}

我在写这行代码的时候脑袋里想的是因为每个结点存放的是当前路从哪到哪，然后我的思路是如果某个路它的终点能到达T区的话，由于并不是这条路的起点就必须是s区，主要看它跟s区是不是联通的，只要是联通的，说明能到达这个t区，又由于我把w已经按从小到大的顺序排好了，所以只要找到一条路径能到达终点，那它的拥挤度就是最低的，但后来发现运行的时候没有输出，然后我一直陷入这种思维里，于是请教了别人，发现了我思维里的两个问题：

存在的问题是，判断两个结点是否连通是看两个结点的根是否相同，只要联通的根节点就是一样的，跟那个族谱一样的道理，但是我这个写的代码找的是一个的根节点，然后另一个我判断的是一个元素，一个集合里的元素，很可能不是根节点，一个集合里，只有根节点才具有代表性，其他的都是这个集合里的元素，判断两个元素是否联通，主要是通过判断是否同根，只要属于同一个元素，相互之间就有路径可以互相通往，就是连通的，哦，还有一个错误，就是我后来判断的时候写成了这样：

if(find(p[i].v)==t&&find(p[i].u)==s)

{

cout << p[i].w;

break;

}

这里的问题是t和s并不一定是两个代表元素，两个根节点，询问两个不同集合之间的元素的路径也是完全OK的，主要就是当时对并查集没有一个很清楚的认识，最后，这是AC代码，把判断改到了判断两个结点是否联通的语句块后面了，如果结合后联通的话立马输出结束运行，节省复杂度和时间，下面是AC代码：

#include
using namespace std;
int n, m, s, t;
struct lu
{
    int u;
    int v;
    int w;
}p[100000];
int father[10000];
//int minx=999999;
int find(int x)
{
    if(father[x]!=x)
    {
        return find(father[x]);
    }
    else
        return x;
}
int cmp(const lu&a, const lu&b)
{
    return a.w> n >> m >> s >> t;
    for(int i = 1; i <= n; i++)
    {
        father[i]=i;
    }
    for(int i = 1; i <= m; i++)

    {
        cin >> p[i].u >> p[i].v >> p[i].w;
    }
    sort(p+1, p+m+1, cmp);
    for(int i = 1; i <= m; i++)
    {
        int fx=find(p[i].u);
        int fy=find(p[i].v);
        if(fx!=fy)
        {
            father[fx]=fy;
        }
        if(find(s)==find(t))
        {
            cout << p[i].w ;
            return 0;
        }

    }
    
   // cout << minx;
    return 0;

}

很简单的题，由于知识点理解不透彻所以最开始做起题来有一种云里雾里的感觉，还是要多看，多做，多练，方法是外壳，思想是内核。反思、总结、内化、提升永远是自己一个人的事。