第十周总结

这周也没看什么东西,我感觉也没什么东西从我脑子里流出来,看过之后,没什么特别的感觉,并查集,拓扑排序,不就那些东西吗,只不过在做题时应用不同而已,套路与灵光一现的结合,当然做的多了,思考时有一些方向(好像我在说废话),算法不都这个样吗!,并查集,合并与查找,拓扑排序:将AOV网中的顶点排成一个线性序列;

并查集:

曾经有位牛人对我说,并查集非常简单(我也这么认为),但是在做题时往往想不到用并查集的思想;

现在我还体会不到(懂的都懂),但是在做题时,看了题目的标签,确实有其他的做题方向,但是其他方向好像并没有比并查集简单(也可能是我太菜了),就这吧,我要开始了

最简单的题(那几十题中,我认为的,我想应该能明白我是啥意思):

修复公路

N个点,M条边,每个边有相应的权值,这些边同时修复,权值代表修复时间,求出这些点连通的最短时间,

题解:

根据修复时间的长短进行升序排序,再进行合并,一旦发现已经连通,就输出

#include

using namespace std;

struct node
{
    int x,y,t;
}bns[100000+10];
int n,m,fa[100000+10];
bool cmp(node a,node b)
{
    return a.t>n>>m;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>bns[i].x>>bns[i].y>>bns[i].t;
    }
    sort(bns+1,bns+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        hb(bns[i].x,bns[i].y);
        if(check())
        {
            cout< 
当然这只是个最简单的题目,比赛中一定不会遇到这么简单问题,
 
其他的什么删边,欧拉回路,还有连通块,这都是什么牛马呀,
 
还有一个就那个炸铁路那个问题,题目虽然理解起来非常简单,不出意外的话,意外就来了,我不会做,代码改了又改,真是无语,最后我还是败给了现实,看了题解;
 
拓扑排序
 
它不认识我,我不懂它(我想起来了一句台词:真正的懂,不用说),但是迫于现实,我还是说说吧,一个有向无环图,算了吧,没什么想说的,本来就没看多少文章,未完待续~~~~