大致题意:
给出一个有向图的传递闭包矩阵,求出这个图至少有多少条边。
大致思路:
对这个图先用Tarjan缩点,再对缩点后的图求一遍floyd求出至少需要多少条边。
#include<iostream>
#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int inf=1<<30;
const int nMax=30015;
const int mMax=500100;
class edge{
public:
int u,v,nex;
};edge e[mMax];
int k,head[nMax];//head[i]是以点i为起点的链表头部
void addedge(int a,int b){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b
e[k].u=a;
e[k].v=b;
e[k].nex=head[a];
head[a]=k;k++;
}
int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep,num[nMax]; //atype 强连通分量的个数
bool insta[nMax];
void Tarjan(int u){ //我的Tarjan模版
int i,j;
dfn[u]=low[u]=++dep;
sta[++top]=u;
insta[u]=1;
for(i=head[u];i;i=e[i].nex){
int v=e[i].v;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else{
if(insta[v])low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
atype++; //强连通分量个数
do{
num[atype]++;
j=sta[top--];
belon[j]=atype; //第j个点属于第type个连通块
insta[j]=0;
}while(u!=j);
}
}
void init(){
k=1;
dep=1;
top=atype=0;
memset(insta,0,sizeof(insta)); //是否在栈中
memset(head,0,sizeof(head)); //静态链表头指针
memset(low,0,sizeof(low)); //Tarjan的low数组
memset(dfn,0,sizeof(dfn)); //Tarjan的dfn数组
memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量
memset(num,0,sizeof(num));
}
int map[300][300];
int main(){
int n,m,i,j,a,b,c,ans;
while(cin>>n){
memset(map,0,sizeof(map));
ans=0;
init();
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cin>>a;
if(i!=j&&a){
addedge(i,j);
}
}
}
for(i=1;i<=n;i++){
if(!dfn[i]){
Tarjan(i);
}
}
for(i=1;i<k;i++){
if(belon[e[i].u]!=belon[e[i].v]){
map[belon[e[i].u]][belon[e[i].v]]=1;
}
}
for(i=1;i<=atype;i++){
if(num[i]!=1){
ans+=num[i];
}
}
// for(i=1;i<=atype;i++)
// {
// for(j=1;j<=atype;j++)
// {
// if(map[i][j])ans++;
// }
// }
for(k=1;k<=atype;k++){
for(i=1;i<=atype;i++){
for(j=1;j<=atype;j++){
if(map[i][k]&&map[k][j]&&map[i][j]){
map[i][j]=0;
//ans--;
}
}
}
}
for(i=1;i<=atype;i++){
for(j=1;j<=atype;j++){
if(map[i][j])ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
cpp:我作为学生的C ++宝藏:fire:
floyd warshall algorithm in matlab
Blum、Floyd、Pratt、Rivest、Tarjan__Time bounds for selection.pdfBlum、Floyd、Pratt、Rivest、Tarjan__Time bounds for selection.pdfBlum、Floyd、Pratt、Rivest、Tarjan__Time bounds for selection.pdfBlum...
对于那些不了解Floyd-Steinberg算法目的的人,这是一种将彩色图像转换为黑白图像的算法(NOT GREYSCALE)。 我们什么时候使用这个? 好吧,对于像Amazon Kindle这样的电子墨水显示器,它们无法显示彩色图像,而...
Floyd-Warshall algorithm
floyd算法+matlab计算,对数学建模爱好者有很大的好处~~~~
Floyd-Warshall算法---创建此项目是为了完成CPCS-324最终项目的第一阶段--- 编程语言:JAVA 该程序使用Floyd-Warshall算法在连接的加权图中查找所有对的最短路径即从任何一个顶点到所有其他顶点的最短路径使用的图形...
Floyd's Tortoise and Hare Algorithm (Floyd 龟兔赛跑算法)
本系统采用Dev C++开发平台来进行编写和测试,用到了类、数组、函数,指针、文件的读取存储操作以及DFS算法和所有顶点对的最短路径(Floyd算法)、 图的各种遍历算法等 用无向网表示XX大学的校园景点平面图,图中顶点...
Floyd-And-LCS:使用动态编程方法实现最长公共子序列(LCS)算法,并创建无向完整图,编写程序以使用Floyd算法查找所有对最短路径。 打印所有线对的最短路径及其长度
中国数学建模-数学工具-Floyd最短路算法的MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss......
这个 m 文件实现了 Floyd Steinberg 抖动算法,可以将其视为一种具有额外人类视觉考虑的图像二值化。
WebRTC_Floyd_Steinberg_dithering 使用纯 JavaScript 在 WebRTC 中实现 Floyd-Steinberg 抖动算法 在 [ ] 上查找更多信息 伪代码: > for each y from top to bottom > > for each x from left to right > > > ...
floyd-warshall-cython Floyd-Warshall 算法的有效 Cython 实现,用于在加权有向图中查找所有顶点对之间的最短路径距离。 见接触随时提出任何问题: 阿米特·莫斯科维奇·艾格峰。
Floyd_Warshall_OpenCL 使用 OpenCL 并行实现 Floyd Warshall 算法 该存储库包含使用 OpenCL 语言的 Floyd Warshall 算法的并行实现。 实现是在 Visual Studio Express Edition 2012 中完成的。 要运行代码,请在...
2.领域:floyd算法 3.内容:基于floyd算法的最优截断切割问题matlab仿真 从一个长方体中加工出一个已知尺寸、位置预定的长方体(这两个长方体的对应表面是平行的),通常要经过6 次截断切割.设水平切割单位面积的...
使用Floyd算法,求解点对之间的最短距离。图结构使用邻接矩阵存储。
#Floyd-Warshall 与 MPI 并行 Floyd-Warshall 算法通过 Fox 算法使用MPI 的并行实现(在C 中)。 要编译,只需在文件夹中运行make命令。 在运行之前,您需要使用集群配置定义一个文件。 要运行程序,您需要在矩阵...
下面是用Python实现Floyd算法的代码,供大家参考,具体内容如下 # -*- coding: utf-8 -*- Created on Thu Jul 13 14:56:37 2017 @author: linzr ## 表示无穷大 INF_val = 9999 class Floyd_Path(): def __...