Rewinner

图论

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

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

505B - Mr. Kitayuta's Colorful Graph 【并查集】

传送门题意：给你m条无向边，两个端点之间有一个颜色c，询问两点之间有几条用同种颜色连接的道路。方法： ①：最开始我的想法是Floyd，用maps[i][j][k]三维数组表示从 i 到 j 是否能够通过 k 颜色连接。（复杂度为（n^3*m+q*m）居然还过了，难道因为跑的是纯循环嘛。。。...

2019-03-13

0 536

Jamie's Contact Groups HDU - 1669 【二分图多重匹配】

传送门题意：Jamie有很多联系人，但是很不方便管理，他想把这些联系人分成组，已知这些联系人可以被分到哪个组中去，而且要求每个组的联系人上限最小，即有一整数k，使每个组的联系人数都不大于k，问这个k最小是多少？思路：就是一道多重匹配模板题，我们需要二分答案，然后利用匈牙利算法的思想，来寻...

2019-03-07

0 596

差分约束建图【转载】

原博客：https://blog.csdn.net/qq_24451605/article/details/47121853 差分约束系统只是对最短路算法的一种应用，没有什么新的算法，只是对于具体问题的建图方法的确定 ---------------------------------------...

2019-03-05

0 491

POJ 2449 Remmarguts' Date【A*算法 + 第K短路】

传送门 Description "Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. Softly touching his little duck...

2019-03-01

0 419

A and B and Lecture Rooms CodeForces 519E 【LCA】

传送门 Description 在大学里，小A和小B是一对非常要好的朋友，他们经常一起参加比赛。现在，这个大学里有n个教室，这n个教室用n-1个走廊相互连接，因此学生可以从一个教室经过走廊走到任何其他的教室。每天，小A和小B都要讨论一些问题。每次下课以后（小A和小B在不同的地方上课），小...

2019-02-28

0 493

POJ 2763 Housewife Wind 【LCA】

传送门 Description After their royal wedding, Jiajia and Wind hid away in XX Village, to enjoy their ordinary happy life. People in XX Village lived in...

2019-02-27

0 584

ZOJ 3195 Design the city 【LCA】

传送门 Description Cerror is the mayor of city HangZhou. As you may know, the traffic system of this city is so terrible, that there are traffic jams e...

2019-02-26

0 621

POJ 1904 King's Quest【Tanjar】

传送门 Description Once upon a time there lived a king and he had N sons. And there were N beautiful girls in the kingdom and the king knew about ea...

2019-02-25

0 469

POJ 3228 Gold Transportation 【并查集】

传送门 Description Recently, a number of gold mines have been discovered in Zorroming State. To protect this treasure, we must transport this g...

2019-02-25

0 446

Proving Equivalences 【HDU-2767】强连通分量+Tanjar缩点

传送门题意：问至少增加多少有向边能将图变成强连通图？思路：如果存在强连通分量，那么我们可以将这个分量看作一个点（一个点也是强连通分量），利用tanjar缩点将原本复杂的图转化为多个DAG如何将这些DAG连接起来变成强连通图呢？ans=max(入度=0点的数量，出度=0点的数量) ///...

2019-02-24

0 419