308宿舍的鶸

Floyd-Warshall的基本思想: 通过一个中转点不断地来松弛顶点的出边 //Floyd-Warshall算法核心语句 for (int k = 1; k <= V; k++) for (int i = 1; i <= V; k++) for (int j = 1; j <= V; j++) if ( e[

思路：先缩点处理，之后就比较难了，因为要选一条边逆向走，总不能用枚举的方法来做把，考虑到缩点后的图必然是一个DAG（有向无环图），于是我们只需要考虑两类点：第一类点：能够从草场1所在的点到达的点第二类点：能够从所在点到达草场1的点那么我们只要求出从草场1所在点走到每个第一类点的最大收益Ai和从从二类点所在点走到一类点的最大收益Bi即可求出答案前者是很容易求的，但是后者怎么求呢？很简单，只需要将图反...

分析:如果一群奶牛在一个强连通分量中，那么它们都是相互喜欢的，所以先用tarjan缩点，那么要怎么才能找到被所有奶牛喜欢的奶牛群呢？这里我们用到一个结论在有向无环图中，如果有且仅有一个点的出度为0 （没有指向其他点的边），那么该点可以被所有点遍历到；反之，该图中没有可以被所有点遍历到的点并且，在有向图无环中，如果一个点可以被所有点遍历到，那么这个点的出度为0所以我们只要在缩点后找出唯一的出度为0的...

分析:求最少需要去掉几个点让源点无法到达汇点,于是就成了一个最小割点问题,我们将一个点拆分成两个点,设这个点为i,那么将i拆分成i和i+n这两个点,连一条i到i+n的有向边,边权为1,将i的入边与i连接,i的出边变为i+n的出边,权值均为无穷大,之后直接求最大流即为最小割点的答案了#include &lt;iostream&gt; #include &lt;cstring&gt; #include...

分析:一道求二分图最大匹配的题,就是建模比较绕其他没什么,首先我们要清楚人和床是需要分开的,所有需要2*n个结点,我们把前1~n结点当成人,n+1~2*n结点当成床,那么问题就简单了,我们只需要将床与汇点连接,需要床的人与源点连接,再将人与自己的床以及认识的人的床连接即可,最后求出的最大流如果与需要床的人数相同的话就可以使每个人都有床睡#include &lt;iostream&gt; #incl...

分析：给定一个有向图，求出最大的强连通分量#include &lt;iostream&gt; #include &lt;cstdio&gt; #include &lt;vector&gt; #define Min(a,b) a&lt;b?a:b #define Max(a,b) a&gt;b?a:b using namespace std; const int maxn = 1e5+10; /*...

思路：看完题目思考了一会后就想到判环即可，统计记录环的长度。#include &lt;iostream&gt; #include &lt;cstdio&gt; using namespace std; const int maxn = 200000+10; int par[maxn], dis[maxn]; int n, temp, ans = 0x3f3f3f3f; void init(in...

今天C语言课写完实验报告就开始做题，然后只想了思路，没有写代码，下午物理实验课回来把代码写上再修改了一下就AC了。思路: 用dfs将图染色，只需染两种颜色,如果遇到已经染色过的点，判断该点的色彩与领边点的色彩是否一样，如果一样的话那么就输出"Impossible"，染色的同时统计每种颜色的数量，较小的那个数量即为答案，但是第一次交的时候我没有想到可以分成被多个图，于是统计的是全图的颜色，正确的做法...

这题有三种解法，1.搜索 2.最短路 3.DP1.直接写个DFS就行了#include &lt;iostream&gt; #include &lt;cstdio&gt; using namespace std; const int maxn = 200+10, inf = 0x3f3f3f3f; int k[maxn], ans = inf; bool vis[maxn]; int n, a, ...

思路:求强连通分量的模版题, 答案就是结点个数大于1的强连通分量的个数#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cstdio&gt; #include &lt;stack&gt; #define sz size() #define Min(a,b) a&lt;b?a:b using namespace std; ...

第一部分------求强连通分量1.强连通分量的概念"有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi&gt;vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected compon...

分析：根据"任意两个配备了一条卫星电话线路的哨所（两边都ᤕ有卫星电话）均可以通话，无论他们相距多远"和可安装的卫星电话的哨所数为s可知只需要将这些哨所连城s个联通块即可，所以只需要贪心将当前剩余最短的边加入生成树并记录生成树中最长的边至剩余s个联通块即可得出答案。#include &lt;algorithm&gt; #include &lt;iostream&gt; #include &lt;ve...