Pikachu_杨京

分类

动态规划(1) 并查集(2) 搜索(3) 最小生成树(2) 最短路径(3) 未归档(24) 欧拉路径(1) 线段树(2) 背包问题(1) 贪心(2) 题解(3)

/ 注册

全部文章（共44篇）

最短路算法 Dijkstra

Dijkstra算法：一个顶点到其余各顶点的最短路径算法。伪代码： vis[i]=0; d[i]=图中边s-i的权值;无s-i边则d[i]=MAX；d[s]=0; 标记s; 循环n-1次{ 找出未被标记中最小的d[x]; 标记x点; 更新d[i],d[i]=min(d...

2019-03-18

0 674

P3371 【模板】单源最短路径（弱化版）

题目：P3371 【模板】单源最短路径（弱化版）题目背景本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。题目描述如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。输入输出格式输入格式：第一行包含三个整数N、M、...

2019-03-17

0 711

P2921 在农场万圣节Trick or Treat on the Farm 并查集

P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm 题目描述每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。由于牛棚不太大，FJ通过指定奶...

2019-03-15

0 503

P1341 无序字母对欧拉路径

题目：P1341 无序字母对题目描述给定n个各不相同的无序字母对（区分大小写，无序即字母对中的两个字母可以位置颠倒）。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。输入输出格式输入格式：第一行输入一个正整数n。以下n行每行两个字母，表示这两个字母需要相邻...

2019-03-14

0 566

P1330 封锁阳光大学并查集解法 dfs解法

P1330 封锁阳光大学题目描述曹是一只爱刷街的老曹，暑假期间，他每天都欢快地在阳光大学的校园里刷街。河蟹看到欢快的曹，感到不爽。河蟹决定封锁阳光大学，不让曹刷街。阳光大学的校园是一张由N个点构成的无向图，N个点之间由M条道路连接。每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点...

2019-03-12

0 569

并查集

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。初始化： for(int i=0;i<n;i++){ p[i]=i;//每个点单独为一个集合（自...

2019-03-09

0 446

并查集 POJ - 1182 食物链

食物链 #include<bits/stdc++.h> using namespace std; #define maxn 50005 int n,k;//n个动物，k句话 int d,x,y;//x y间关系为d int p[3*maxn];//集合 int ans...

2019-03-07

0 568

并查集+kruskal P1111 修复公路

P1111 修复公路题目求最早什么时候任意两个村庄能够通车，将每个村庄看成一个顶点，只要找到这些顶点构成的最小生成树，就可找到通车的最小代价。 kruskal算法求最小生成树，每次选择权最小的边，并且所有选择的边不能形成环，直到找到n-1条边将n个点连接起来，构成最小生成树。上述中使...

2019-03-06

0 478

并查集 P2661 信息传递

P2661 信息传递题目描述有 n 个同学（编号为 1 到 n ）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为 i 的同学的信息传递对象是编号为 Ti 的同学。游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各...

2019-03-05

0 587

P1101 单词方阵

P1101 单词方阵 #include<bits/stdc++.h> using namespace std; struct way{ int x,y; }w[7];//记录路线 int n; char str[100][100],a[8]="yizhong"...

2019-03-05

0 507