@Angela-Balzac
2017-12-22T12:15:42.000000Z
字数 2756
阅读 752
使用Tarjan算法或Kosaraju算法。
当然我们主要使用Tarjan啦。
Tarjan模板
void tarjan(int x){
dfn[x]=low[x]=++idx;
s[++top]=x;
in[x]=1;
for(int u=head[x];u;u=edge[u].next){
int t=edge[u].to;
if(!dfn[t]){
tarjan(t);
low[x]=min(low[x],low[t]);
}
else if(in[t]){
low[x]=min(low[x],dfn[t]);
}
}
if(dfn[x]==low[x]){
tot++;
while(s[top]!=x){
ans[tot].push_back(s[top]);
in[s[top]]=0,top--;
}
ans[tot].push_back(s[top]);
in[x]=0,top--;
}
}
Tarjan完了过后当然要缩点。
那是很简单的。
题意
给出一个有向图G，问有多少个大小>1的强连通分量。
解析
Tarjan弹出的时候记录弹出数量即可。
题意
给出一个有向图，问有多少个点能被所有点到达。
解析
先缩点，然后看有多少出度为零的点，一个点的话就选中。
题意
给定n对夫妻关系，再给定m对情人关系。
如果在第i对夫妻离婚的前提下，这些人仍然能组成n对夫妻(情人可以结为夫妻)，就称i这个婚姻是不稳定的。
要求判断每一对婚姻稳不稳定。
解析
缩点，在环内即不稳定。
割点和桥
无向图G中，若去掉点x及其所有相邻的边之后，G的连通块个数增加了，则称x是G的一个割点。
无向图G中，若去掉边e之后，G的连通块个数增加了，则称e是G的一个桥。
怎么求割点？
类似之前的tarjan算法。
如果点x有一个出点的low值>=dfn[x]，则x是一个割点。
必须注意特殊情况：第一个搜索的点。
双连通分量
对于一个无向图G，若其不存在桥，则称其是一个边双连通图
一个无向图G的极大边双连通子图成为G的边双连通分量。
对于一个无向图G，若其不存在割点，则称其是一个点双连通图
一个无向图G的极大点双连通子图成为G的点双连通分量。
怎么求双连通分量？
还是用Tarjan算法，几乎和求强连通分量的方式一样。
为什么这样做是对的？
从DFS树的角度考虑，我们把树边当成从上到下的有向边，非树边当成从下到上的有向边，这个图中的强连通分量就是正常无向图中的边双连通分量。
点双连通分量的求法
由于一个割点可能在多个点双连通分量里，所以我们需要在普通的tarjan算法基础上做一些改动。
我们尝试把边压入栈中而不是点，这样我们开始弹栈的时候最后剩下的这条边就会把割点留下了。
题意
为了从F(1≤F≤5000)个草场中的一个走到另一个，贝茜和她的同伴们有时不得不路过一些她们讨厌的可怕的树。奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。
每对草场之间已经有至少一条路径。给出所有R(F-1≤R≤10000)条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量,路径由若干道路首尾相连而成。两条路径相互分离，是指两条路径没有一条重合的道路。但是，两条分离的路径上可以有一些相同的草场。对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。
解析
缩边成树，连接叶子节点，边数为(叶子节点数)。
关于二分图的更多知识:Week17 总结
Hall定理
有二分图G=(V,E)，其中V划分为A,B，C是A的子集，且|C|=k，
存在一个匹配M使得C中的每一个点都存在于匹配中，当且仅当对于∀1<=i<=k，C中任意i个点都至少和B中i个点相连。
必要性显然。
充分性：假设对于i小于k全部成立且k不成立。先找到一个C的最大匹配，此时有一个点不在匹配当中，由于i=1成立，所以至少有一个点在B中并且和他关联，且这个点必须已经在匹配中，那么我们再找到和这个点匹配的点，由于i=2成立，所以至少有两个点在B中并且和它们相连，然后那个点也必须已经在匹配中······最后得出B中至少有k个点在匹配中，这和C中只有k-1个点在匹配中矛盾。
题意
第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2名飞行员，其中1名是英国飞行员，另1名是外籍飞行员。
在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
解析
裸模板。
题意
贝茜想驾驶她的飞船穿过危险的小行星群。小行星群是一个NxN的网格(1≤N≤500)，在网格内有K个小行星(1≤K≤10000)。幸运地是贝茜有一个很强大的武器，一次可以消除所有在一行或一列中的小行星，这种武器很贵，所以她希望尽量地少用。给出所有的小行星的位置，算出贝茜最少需要多少次射击就能消除所有的小行星。
解析
我们把对行和列建一个二分图，若存在小行星(i,j)，就在行i和列j之间连一条边。
现在问题就转化为了求二分图最小点覆盖。
直接跑匈牙利算法即可。
题意
大雨侵袭了牧场，牧场是一个 R * C 的矩形，其中 1≤R，C≤50。
大雨将没有长草的土地弄得泥泞不堪，可是小心的奶牛们不想在吃草的时候弄脏她们的蹄子。为了防止她们的蹄子被弄脏，农场主决定在泥泞的牧场里放置一些木板．每一块木板的宽度为1个单位，长度任意．每一个板必须放置在平行于牧场的泥地里。农场主想使用最少的木板覆盖所有的泥地。
一个木板可以重叠在另一个木板上，但是不能放在草地上。
解析
类似之前的那道题，区别在于这道题不能盖住好的草坪。
首先能想到贪心，即每块板子延伸至能盖的最长情况。
所以对于一个泥坑，他就一定要被横着或竖着的两块板子的至少一块来覆盖，这就很像之前的最小点覆盖了。
所以我们建二分图，A部是所有横着的板子，B部是所有竖着的板子，然后对于所有泥坑，把他相关的两个板子连起来，这样选择一个点就代表选择了一块板子，最小点覆盖就相当于用最小的板子数来覆盖所有泥坑了。