Category Archives: 图论

ACdream 1103 瑶瑶正式成为CEO (树链剖分,费用流)

一颗n个点的有向边树,这个基础上添加了m条有向边,变成一个DAG。每条边都有ai, bi, ci, di,di …

CCPC长春E题 (xjb搞)

给出一个n条边的n个点的无向连通图,求一个条路径使得经过所有点并且经过的距离最短,每条边边权都是1. 其实这就 …

Codeforces 716D Complete The Graph (二分,最短路)

给出一张图,没有重边自环,有些边可以重新设置权值,构造一个方案使得最短路长度是L 我们可以先令可以重设置边的权 …

2016 ACM/ICPC Asia Regional Qingdao Online

1001 – I Count Two Three 水题,大表+二分即可 1002 –  …

LightOJ 1177 Angry Programmer (最小割,水题)

n个点,m条边的图,删除每个点和每条边都需要费用,但是点1和n不能删除,求最少费用让1个n不连通。 一眼题,这 …

2016 ACM/ICPC Asia Regional Dalian Online

首先总结下这次大连网赛,总算了却了一直的担忧,把名额最少的大连打下来了。这场网赛给我的感觉就是“痛并快乐着”, …

CSU 1806 Toll (辛普森,最短路)

给出10个点的图,每条路的花费会根据时间t发生改变即:c * t + d,这个人通过每条路都不需要时间,f(t …

CSU 1808 地铁 (最短路)

有若干条地铁线路,有n个车站,m段路,第i段路处于ci铁路线,且连接着ai和bi需要ti的时间。如果某一个人从 …

CSU 1804 有向无环图 (拓扑,dp)

给出一个图,每个点有两个权值ai,bi,count(i, j)表示i到j的路径条数,计算上面这个式子。 我们可 …

CodeForces 164C Machine Programming (费用流)

给出n个任务,它的工作时间si~ti,有K台机器,如果机器选择了某个任务就一定要从头做到尾。每个任务有一定报酬 …