18XiWenjuan

图论

dp(29) MFC(5) STL(6) 分治(2) 博弈(6) 字符串(4) 思想(14) 思维(33) 搜索(10) 数据结构(12) 数论(45) 日常小技巧(1) 暴力|模拟(30) 未归档(12) 水|坑(23) 深度学习(2) 计算几何(6) 计蒜客(1) 赛后补题(22) 题解(2)

/ 注册

全部文章 / 图论（共39篇）

luogu P1251 餐巾计划问题（网络流24题费用流 + 拆点建图）

题目描述一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_iri块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天...

2020-10-02

5 606

sdnu1015.最远路径(dfs）

Description 有一棵有n个节点的二叉树，它的节点编号为1到n，根节点编号是1，它的每条边都有一个给定的长度。请你求出该二叉树中距离根节点最远的节点的距离。 Input 第1行：一个数字n(1 <= n <= 100)，表示该二叉树节点的数量。第2至第n+1行：每行有三个...

2020-09-21

0 511

sdnu1351.the Number of Department（并查集模板）

Description Company A has N employees, this company has lots of departments around the country. The employees who belong to different departments...

2020-09-21

0 516

最短路模板（Floyd && Dijkstra优化 && Bellman-Ford && spfa优化）

1.Floyd #include <bits/stdc++.h> using namespace std; const int N=1e4+50; const int inf=0x3f3f3f3f; int g[N][N],n,m; void floyd() { for(int...

2020-09-21

0 531

最小生成树模板（kruskal&&prim）

1.kruskal 最小生成树能够保证首先是树（对于n个顶点的图只有条n - 1边），其次保证任意两个顶点之间都可达，再次保证这棵树的边权值之和为最小，但不能保证任意两点之间是最短路径；（最后求出来的路径长度是经过n个顶点的) 最小生成树是到一群点（所有点）的路径代价和最小，是一个n - 1...

2020-09-21

0 481

HDU - 2066 一个人的旅行（floyd/dijkstra)

虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖...

2020-09-21

0 727

poj3169 Layout（差分约束 spfa最短路）

Description Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N ...

2020-09-21

0 415

HDU - 6252 Subway Chasing （差分约束 spfa最长路）

Mr. Panda and God Sheep are roommates and working in the same company. They always take subway to work together. There are NN subway stations on their...

2020-09-21

0 715

差分约束简陋总结

1.最短路将不等式转化为x[i]-x[j]<=c的形式。对结点j和i建立一条j--->i的有向边，权值为c 所求x[n-1]-x[0]的最大值即从0到n-1的最短路。（a-b<c写成a-b<=c-1） const int inf=0x3f3f3f3f（初始化为...

2020-09-21

0 420

POJ - 2253 Frogger（路径最大值的最小值）

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but ...

2020-09-21

0 593