0 会飞的小蛇

尚未进行身份认证

暂无相关简介

等级
TA的排名 12w+

(最小生成树)AcWing346 走廊泼水节

AcWing346 走廊泼水节思路:他要求最小生成树不能改变,我们想一下kurskal的过程,是选两个点,判断他是否在一个并查集中,不是的话就合并,加权值。那么如果加上其他的边但依旧要让这两个点合并,我们可以看出加入的边权值要大于这条边权值w,所以最小的权值为w+1。我们又可以考虑到这两个点的子树分别有x和y个结点,那么加边的时候我们可以加x*y-1条边。所以我们可以得到结果为 ∑(x*y-...

2020-01-24 19:08:45

(强连通分量)洛谷P2341【模板】强连通分量 / [HAOI2006]受欢迎的牛

洛谷P2341【模板】强连通分量 / [HAOI2006]受欢迎的牛思路:如题目描述,模板题。花了两个小时看了tarjan,然后看了题目。what?excuse me?为啥跟我看到的东西感觉不太一样?然后看了大佬的题解,what?为啥叫容易看出,为啥我看不出?啥叫强连通分量呢,简而言之,一个图的子图中任意两点可以相互到达。(就是构成了一个环)。下面说tarjan算法。其中两个重要的数组...

2020-01-24 17:05:11

(最小生成树)洛谷P2330 [SCOI2005]繁忙的都市

洛谷P2330 [SCOI2005]繁忙的都市思路:模板题。代码:#include<bits/stdc++.h>#define pii pair<int,int>#define ll long long#define cl(x) memset(x,0,sizeof(x))const int N=1e6+10;const int mod=1e7+9;con...

2020-01-24 11:36:58

(最小生成树)HDU1875畅通工程再续

HDU1875畅通工程再续思路:模板题。代码:#include<bits/stdc++.h>#define pii pair<int,int>#define ll long long#define cl(x) memset(x,0,sizeof(x))const int N=1e5+10;const int mod=1e7+9;const int max...

2020-01-24 10:59:08

(最小生成树)AcWing1146新的开始

AcWing1146新的开始思路:本来是跑一边最小生成树再加上发电站的最小值,但是wa了。后来可以想到如果发电站的值很小,建设电网的费用很大,就可以建多个发电站。所以我们将图转化成n+1个点的图,设一个虚拟的点,他到其他点的权值为建发电站的费用。代码:#include<bits/stdc++.h>#define pii pair<int,int>#define...

2020-01-24 00:32:55

(最小生成树)HDU1233还是畅通工程

HDU1233还是畅通工程思路:模板题。可是我竟然把&&打错成&,wa了n次!!!#代码:#include<bits/stdc++.h>#define pii pair<int,int>#define ll long long#define cl(x) memset(x,0,sizeof(x))const int N=1e6+10;...

2020-01-23 20:39:20

(带权并查集)洛谷P1525关押罪犯

洛谷P1525关押罪犯思路:犯人之间的关系我们可以用一个数来表示,0表示在一个监狱里,1表示不在一个监狱里。为了使最大值尽可能小,我们先从大到小排序。然后并查集,依次判断两个人的父节点是否相同(存在关系),如果不存在就合并;存在就判断两个人是否在同一个监狱,在就输出两个人的矛盾值。代码:#include<bits/stdc++.h>#define pii pair<in...

2020-01-23 20:06:17

(最小生成树)POJ1258Agri-Net

POJ1258Agri-Net题意&思路:给n个农场之间的距离,要铺设光缆使之两两连通,问最小铺设光缆的距离。模板题。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<string.h>#inc...

2020-01-23 19:14:06

(最小生成树)POJ1751Highways

POJ1751Highways题意&思路:给你n个城市的坐标,m组已经连通的城市,使两两城市连通的需要修的道路的总和最小,输出修建公路的两城市的坐标。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<st...

2020-01-23 19:03:42

(最小生成树)POJ2349Arctic Network

POJ2349Arctic Network题意&思路:给你p个点和s-1条免费边,问使两两点连通的最小的最长边。求第p-s条最长边,kruskal。用%lf记得交c++。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#in...

2020-01-23 17:45:24

(最小生成树)POJ1789Truck History

POJ1789Truck History题意&思路:给你n个长度为7的字符串,每两个字符串之间的权值为相同位置字符不同的个数。每个字符串都由另一个字符串变化而来,变化的质量为1/权值和。求最大质量。其实就是求最小权值和。模板题。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>...

2020-01-23 01:55:05

(最小生成树)POJ2421Constructing Roads

POJ2421Constructing Roads题意&思路:何以解忧,唯有做题。为什么总是想复杂。给n个村庄和村庄之间的距离,有些村庄已经存在一条路。问使村庄之间两两连通最少需要修路的长度。并查集和最小生成树,模板题。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#in...

2020-01-23 01:34:28

(最小生成树)POJ2031Building a Space Station

POJ2031Building a Space Station题意&思路:给你n个球的球心坐标(x,y,z)和半径r,如果两个球相交则视为连通。问使所有球两两连通(表面接触)的最短道路。模板题。注意点就是两两连通就是两个球的距离设为0,以及提交时用C++才能交%lf。代码:#include<iostream>#include<stdio.h>#incl...

2020-01-22 22:29:45

(最小生成树)POJ1287Networking

POJ1287Networking题意&思路:给一个区域内p个点和r个电缆,问使两两连通的最小长度。模板题。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<string.h>#include&...

2020-01-22 22:01:25

(最小生成树)POJ1251Jungle Roads

POJ1251Jungle Roads题意&思路:一个旅游景点需要造缆车,使任意两个景点都可以相互到达,问最小花费。最小生成树(kurskal)模板题,只需要把字母改成整型就好了。代码:#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm&gt...

2020-01-22 21:48:54

(BFS+状压)AcWing1131拯救大兵瑞恩

AcWing1131拯救大兵瑞恩思路:先想到是用一个结构体存一个格子四周的情况和钥匙的情况,然后每次遇到门的时候要把自己有的钥匙和需要的比较。但后来想到钥匙最多只有十个,所以可以用状态压缩,每个点的钥匙和自己的钥匙可以用二进制数表示,拿钥匙就用按位或;遇到门就用按位与判断。然后我又用结构体记录一个点四周是否有墙,结果愉快的MLE了。后来把数据自己测的时候发现跑不出结果。在后面的一个小时内,我...

2020-01-21 21:31:17

(并查集)洛谷P1197 [JSOI2008]星球大战

P1197 [JSOI2008]星球大战思路:摧毁是这个题目的一个难点,如果是摧毁一个点就重新构图的话肯定会T。那么我们可以反着想,就是从最后的状态往前推,用并查集判断是否是连通块。代码:#include<bits/stdc++.h>#define pii pair<int,int>#define ll long longconst int N=1e6+10;...

2020-01-20 20:04:42

(SPFA的SLF优化)AcWing342道路与航线

AcWing342道路与航线思路:看起来非常裸的spfa,然而精心构造的数据卡了。就用到spfa的SLF优化,我们之前的spfa都是用队列实现的,每个数据都放到队尾。现在我们用双端队列,如果当前点的权值少于我们当前队头点的权值的话,那么我们就将这个节点插入到队头,否则我们插入到队尾。代码:#include<bits/stdc++.h>#define pii pair<...

2020-01-20 18:02:50

(dp) 牛客小白月赛21I I love you

牛客小白月赛21I I love you思路:dp。dp[i]=(dp[i]+(s==‘x’)*dp[i-1])%mod。x为当前位置上要求的字母。代码:#include<bits/stdc++.h>#define pii pair<int,int>#define ll long longconst int N=1e6+10;const int mod=2...

2020-01-19 08:33:33

(贪心)洛谷P1233木棍加工

洛谷P1233木棍加工思路:排序,l,w按照从大到小排列。然后递归寻找。(据说也可以用dp做)。代码:#include<bits/stdc++.h>const int N=1e4+10;const int mod=1e7+9;const int maxn=0x3f3f3f3f;const int minn=0xc0c0c0c0;const int inf=999999...

2020-01-18 17:04:35

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条Blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发。