考虑这样一个问题:
老师想通知他的所有学生一个消息,虽然他手上有他们的联系方式,但是一个一个联系太耗时间和电话费了。他知道其它人也有一些别人的联系方式,这样可以通知他人,再让他们去通知一下别人。现在要求出至少需要联系多少人,最少需要多少花费,使得所有的人都被通知到。
上述问题可以抽象为:图G中,每个点都有一个权值,若a能联系到b,则连边(a,b)。选出最少的点数(或者权值最小),使从这些点能到达所有点。
解:求图G的强连通分量,入度为0的强连通分量个数即为最小点基,从每个入度为0的强连通分量中取出权值最小的点,构成的集合即最小权点基。求强连通Trajan算法不再赘述。
例:HDU1827
/*
最小点基和最小权点基:
最小点基=从每个入度为0的SCC中任意选出一个点的集合
最小权点基=从每个入度为0的SCC中选出最小权值的点的集合
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int MAX = 1005;
int n,m;
int node[MAX];
struct Edge
{
int from;
int to;
int next;
};
Edge e[2005];
int head[MAX],edgeNum;
int dfn[MAX],low[MAX],seq;
int stack[MAX],top;
bool inStack[MAX];
int belong[MAX],cnt;
int ind[MAX];
int cost[MAX];
void addEdge(int from, int to)
{
e[edgeNum].from = from;
e[edgeNum].to = to;
e[edgeNum].next = head[from];
head[from] = edgeNum++;
}
int min(int a, int b)
{
return a<b?a:b;
}
void Tarjan(int u)
{
dfn[u] = low[u] = seq++;
stack[top++] = u;
inStack[u] = true;
for(int i = head[u]; i != -1; i = e[i].next)
{
int w = e[i].to;
if(dfn[w] < 0)
{
Tarjan(w);
low[u] = min(low[u],low[w]);
}
else if(inStack[w])
low[u] = min(low[u],dfn[w]);
}
if(dfn[u] == low[u])
{
int v;
cnt++;
do
{
top--;
v =stack[top];
inStack[v] = false;
belong[v] = cnt;
}while(u != v);
}
}
void solve()
{
int i;
for(i = 1; i <= n; i++)
if(dfn[i] < 0)
Tarjan(i);
for(i = 0; i < edgeNum; i++)
{
if(belong[e[i].from] != belong[e[i].to])
ind[belong[e[i].to]]++;
}
for(i = 1; i <= n; i++)
{
if(cost[belong[i]] > node[i])
cost[belong[i]] = node[i];
}
int result1=0,result2=0;
for(i = 1; i <= cnt; i++)
{
if(ind[i]==0)
{
result1++;
result2 += cost[i];
}
}
printf("%d %d\n",result1,result2);
}
int main()
{
int i;
int from,to;
while(scanf("%d %d",&n,&m)!=EOF)
{
edgeNum = seq = cnt = top = 0;
memset(head,-1,sizeof(head));
memset(dfn,-1,sizeof(dfn));
memset(inStack,0,sizeof(inStack));
memset(ind,0,sizeof(ind));
for(i = 1; i <= n; i++)
cost[i] = INF;
for(i = 1; i <= n; i++)
scanf("%d",&node[i]);
for(i = 0; i < m; i++)
{
scanf("%d %d",&from,&to);
addEdge(from,to);
}
solve();
}
return 0;
}
分享到:
相关推荐
然后,和有向图相似的介绍了两种无向图的遍历方法(深度优先遍历和广度优先遍历)。接着介绍了迷宫问题的求解方法。最后,介绍了求解最短路径的六种方法,包括宽度优先搜索、动态规划、A﹡算法、等代价搜索法、...
该资源为C++算法——图算法(第三版)PDF版本,包括图搜索、有向图和无环向图、最小生成树、最短路径、网络流
也就是说,任何一个ICG游戏都可以通过把每个局面看成一个顶点,对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义SG(Sprague-Garundy)函数。 SG函数的建立 首先...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
《C#全能速查宝典》共分为8章,分别介绍了C#语言基础、Windows窗体及常用控件、Windows高级控件、控件公共属性、方法及事件、数据库开发、文件、数据流与注册表...,共包含562个C#编程中常用的属性、方法、类和各种技术...
分别对有向图、无向图、带权有向图、带权无向图实现对图的基本操作(创建、求顶点的度数、增加/删除边、判断边是否存在、DFS、BFS、判断是否连通、连通构件的标识,求生成树等)。 代码中还实现了顶点的增删、图的...
8. 有向图最小点基(邻接阵形式) 46 七. 图论_应用 46 1.欧拉回路(邻接阵形式) 46 2. 前序表转化 47 3. 树的优化算法 48 4. 拓扑排序(邻接阵形式). 49 5. 最佳边割集 50 6. 最佳顶点割集 51 7. 最小边割集 52 8. 最小...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
图论算法(兼容有向图,无向图):广度和深度优先遍历、确定图是否存在回路、拓扑排序、强连通分支、欧拉环(欧拉路径)、最小生成树(Kruskal、Prim)、单源最短路径(3种)、每对顶点间最短路径(2种)、最大流(2...
图论算法(兼容有向图,无向图):广度和深度优先遍历、确定图是否存在回路、拓扑排序、强连通分支、欧拉环(欧拉路径)、最小生成树(Kruskal、Prim)、单源最短路径(3种)、每对顶点间最短路径(2种)、最大流(2...
1.选择图的类型(无向图或有向图),默认为无向图。 2.画结点。选择菜单'画图'中的'结点'或快捷键'结点'后,在画图区点击鼠标左键即可( 在画错的地方单击右键,可对其删除)。 3.画直线,即对以上的结点进行连线。选择...
图论算法(兼容有向图,无向图):广度和深度优先遍历、确定图是否存在回路、拓扑排序、强连通分支、欧拉环(欧拉路径)、最小生成树(Kruskal、Prim)、单源最短路径(3种)、每对顶点间最短路径(2种)、最大流...
新版中不仅涵盖了新的主题,而且还提供了对许多经典算法的更充分的解释,包括图的性质、图搜索、有向图、最小生成树、最短路径和网。《算法:C语言实现(第5部分)图算法(原书第3版)》涵盖了足够的基本内容及较详细的图...
其中向左键使Column向左移,向右键使Column向右移,向下键使Column快速下降,向上键使Column方块交换顺序,空格键在暂停与继续之间切换。游戏将根据得分的多少来加快Column的下降速度,大约每增加五十分加快10毫秒。...
(2)求有向图的强连通分量(Strong_comp) (3)有向无环图的两个算法 拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点和重...
(2)求有向图的强连通分量(Strong_comp) (3)有向无环图的两个算法 拓扑排序(Toposort) 关键路径(Critical_path) (4)求最小生成树 普里姆算法(Prim) 克鲁斯卡尔算法(Kruscal) (5)求关节点...
其二是点击关闭按钮的时候会直接完全退出而不是后台运行,其实非常不符合我们的使用情况和理念——我们是需要Outlook一直挂在后台以方便第一时间接收到新的邮件的。今天笔者就在这里向大家介绍一下解决的方法。 首先...