图论

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PI; const int INF = 0x3f3f3f3f; const int MAXN = 1500; const...

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PI; const int MAXN = 10010; const int MAXM = 10010; struct...

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PI; const int MAXN = 10020; const int MAXM = 5000010; stru...

算法引入： *求一个图G中的最小环路的朴素算法为:每次找到一条边,删除了求这两点之间的最短路径; *若能求出,则这条最短路径与原来的边构成一个环,不过时间复杂度略高; *算法思想; *Floyd算法是按照顶点的编号增加的顺序更新最短路径的; *如果存在最小环,则会在这个环中的点编号最大的那个点u更新最短路径之前发现这个环; *即当点u被拿来更新i到j的最短路...

题意：~ 思路：给定一个图，几个障碍点，问删除至多一条边能否使得起始位置到不了终点位置，即求最小割。数据范围较大，还卡SAP，ISAP，只能用dinic过？ #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long lo...

题意：~ 思路：缩点之后求个最短路 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PI; typedef pair< P...

题意：~ 思路：先处理出乘坐出租车能到达的点，建图跑最短路即可。 #include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAXN = 100010; const LL INF = 1e18 + 7; const int lowINF...

题意：~ 思路：最小权匹配，跑两遍KM，第二次建边要处理每个工人第一次做工的时间差。 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int>...

题意：~ 思路：如果v能引爆u那么v向u建边。之后用Tarjin强连通缩点，变成有向无环图，将那些入度为0的点的集合求最小引爆带价。 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typ...

题意：在n个点上有着食物，有m条边，除了第一个走的人，其他人都有pi的概率这条边，再大家都能获得食物的前提下，求破坏网络的概率最小。 思路： 每条边有走的次数（流量），每条边走一次发生破坏概率为p（流量1，费用p），容易想到费用流。可是费用流往往是费用相加的，这个是概率，只能相乘。有什么办法，log函数可以把乘除法转换为加减法。所以对每个概率取个log当成费...