Midnightkwai

分类

ACM之路(320) KMP(11) 二分(2) 二叉树(1) 动态规划(19) 博弈(2) 大数(4) 差分(1) 并查集(3) 搜索(23) 数学几何(25) 数据结构(127) 最大匹配(3) 最小生成树(7) 最短路(9) 未归档(100) 枚举(14) 模拟(8) 水题(23) 清欢渡总结(5) 线段树(2) 规律(6) 贪心(9) 递推(5) 题解(1)

/ 注册

全部文章（共730篇）

AcWing - 二分图的最大匹配(匈牙利)

题目链接:https://www.acwing.com/problem/content/863/ 时/空限制：1s / 64MB 题目描述给定一个二分图，其中左半部包含n1个点（编号1~n1），右半部包含n2个点（编号1~n2），二分图共包含m条边。数据保证任意一条边的两个端点都不可能在同...

匈牙利二分图最大匹配

2019-08-17

0 0

AcWing - 染色法判定二分图(染色法)

题目链接:https://www.acwing.com/problem/content/description/862/ 时/空限制：1s / 64MB 题目描述给定一个n个点m条边的无向图，图中可能存在重边和自环。请你判断这个图是否是二分图。输入格式第一行包含两个整数n和m。 ...

二分图染色法

2019-08-16

0 547

AcWing - Kruskal算法求最小生成树(Kruskal)

题目链接:https://www.acwing.com/problem/content/description/861/ 时/空限制：1.500000s / 64MB 题目描述给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不...

Kruskal 最小生成树

2019-08-16

0 0

AcWing - Prim算法求最小生成树(Prim)

题目链接:https://www.acwing.com/problem/content/description/860/ 时/空限制：1s / 64MB 题目描述给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出im...

Prim 最小生成树

2019-08-16

0 574

AcWing - Floyd求最短路(Floyd)

题目链接:https://www.acwing.com/problem/content/description/856/ 时/空限制：1s / 64MB 题目描述给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定k个询问，每个询问包含两个整数x和y，表示查询从点x...

Floyd 最短路

2019-08-16

0 818

AcWing - spfa判断负环(Spfa&邻接表)

题目链接:https://www.acwing.com/problem/content/description/854/ 时/空限制：1s / 64MB 题目描述给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。请你判断图中是否存在负权回路。输入格式第一行包含...

Spfa 判负环

2019-08-16

0 612

AcWing - spfa求最短路(Spfa&邻接表)

题目链接:https://www.acwing.com/problem/content/853/ 时/空限制：1s / 64MB 题目描述给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出imposs...

Spfa 最短路

2019-08-16

0 586

AcWing - 有边数限制的最短路(Bellman_Ford)

题目链接:https://www.acwing.com/problem/content/855/ 时/空限制：1s / 64MB 题目描述给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，...

2019-08-16

0 612

AcWing - Dijkstra求最短路 II(堆优化Dijkstra&邻接表)

题目链接:https://www.acwing.com/problem/content/852/ 时/空限制：1s / 64MB 题目描述给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。输...

堆优化的Dijkstra 最短路邻接表

2019-08-16

0 639

AcWing - Dijkstra求最短路 I(Dijkstra&邻接矩阵)

题目链接:https://www.acwing.com/problem/content/description/851/ 时/空限制：1s / 64MB 题目描述给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出1号点到n号点的最短距离，如果无法从1号点走到n...

Dijkstra 最短路邻接矩阵

2019-08-16

0 818