首页 >  
搜索关键字:无向图    ( 2779个结果
Kruskal算法求最小生成树
给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。 求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。 给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。 由V中的全部n个顶点和E中n-1条边构成 ...
分类:编程语言   时间:2019-07-17 09:25:44    收藏:0  评论:0  赞:0  阅读:12
有向图一定不要跑最小生成树
不然你会死的很惨 有向图不一定连通,无向图不用考虑连通问题 我是个有向图中用kuskal的傻逼。模拟测试10分 那么有向图生成树叫什么呢? 树形图 最小树形图用什么求? 朱刘算法 ...
分类:其他   时间:2019-07-16 13:18:39    收藏:0  评论:0  赞:0  阅读:15
UVA 1599 Ideal Path
题目链接:https://vjudge.net/problem/UVA-1599 题目分析与翻译摘自《算法禁赛入门经典》 题目大意 给一个 n 个点 m 条边(2 ≤ n ≤ 100000,1 ≤ m ≤ 200000)的无向图,每条边上都涂有一种颜 色。求从结点 1 到结点 n 的一条路径,使得经 ...
分类:其他   时间:2019-07-15 23:53:52    收藏:0  评论:0  赞:0  阅读:22
NLP --- 条件随机场CRF详解 重点 特征函数 转移矩阵
上一节我们介绍了CRF的背景,本节开始进入CRF的正式的定义,简单来说条件随机场就是定义在隐马尔科夫过程的无向图模型,外加可观测符号X,这个X是整个可观测向量。而我们前面学习的HMM算法,默认可观测符号是独立的,但是根据我们的实际语言来说,独立性的假设太牵强,不符合我们的语言规则,因此在HMM的基础 ...
分类:其他   时间:2019-07-15 23:43:21    收藏:0  评论:0  赞:0  阅读:21
【2019.7.15】
1.足球联赛 (soccer.pas/c/cpp) hin水 1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<cmath> 6 #include<stack> 7 #in ...
分类:其他   时间:2019-07-15 17:55:53    收藏:0  评论:0  赞:0  阅读:1
欧拉回路
【题目描述】:有一天一位灵魂画师画了一张图,现在要你找出欧拉回路,即在图中找一个环使得每条边都在环上出现恰好一次。一共两个子任务:这张图是无向图。( 50分)这张图是有向图。( 50分)【输入描述】:第一行一个整数 t,表示子任务编号。t∈{1,2},如果 t=1则表示处理无向图的情况,如果 t=2 ...
分类:其他   时间:2019-07-15 13:04:52    收藏:0  评论:0  赞:0  阅读:12
【模板】无向图欧拉回路和欧拉路径判断
题面 版子不多讲 ...
分类:其他   时间:2019-07-15 13:01:32    收藏:0  评论:0  赞:0  阅读:26
无向图的欧拉回路和欧拉路径判断
```cpp #include #include using namespace std; const int MAX_N = 100; const int MAX_M = 10000; struct edge { int v, next; int len; } E[MAX_M]; int p[MA... ...
分类:其他   时间:2019-07-15 12:49:45    收藏:0  评论:0  赞:0  阅读:22
蚂蚁之旅
【题目描述】: 给你无向图的N个点和M条边,保证这M条边都不同且不会存在同一点的自环边,现在问你至少要几笔才能所有边都画一遍。(一笔画的时候笔不离开纸) 【输入描述】: 多组数据,每组数据用空行隔开。 对于每组数据,第一行两个整数N,M表示点数和边数。接下去M行每行两个整数a,b ,表示a,b之间有 ...
分类:其他   时间:2019-07-15 12:35:04    收藏:0  评论:0  赞:0  阅读:15
题解 [BZOJ4144] Petrol
题目描述 ? 有一张 n 个点 m 条边的无向图,其中有 s 个点上有加油站。有 Q 次询问(a,b,c), 问能否开一辆油箱容积为 c 的车从 a 走到 b.(a,b均为加油站) 输入格式 ? 第一行三个整数 n,s,m。 ? 接下来一行 s 个数,表示有加油站的节点。 ? 接下来 m 行,每行三 ...
分类:其他   时间:2019-07-13 00:59:11    收藏:0  评论:0  赞:0  阅读:30
Test 7.12 T2
题目描述 ? 有一张 n 个点 m 条边的无向图,其中有 s 个点上有加油站。有 Q 次询问(a,b,c), 问能否开一辆油箱容积为 c 的车从 a 走到 b。 输入格式 ? 第一行三个整数 n,s,m。 ? 接下来一行 s 个数,表示有加油站的节点。 ? 接下来 m 行,每行三个整数 (x,y,z ...
分类:其他   时间:2019-07-12 23:32:45    收藏:0  评论:0  赞:0  阅读:19
BZOJ 4289 最短路+优化建图
题意:给出一个N个点M条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点1到点N的最小代价。起点的代价是离开起点的边的边权,终点的代价是进入终点的边的边权。 解法:参考https://www.cnblogs.com/zj75211/p/7168254.html这位大佬的 ...
分类:其他   时间:2019-07-12 21:02:04    收藏:0  评论:0  赞:0  阅读:26
We Need More Bosses CodeForces - 1000E (无向图缩点)
大意: 给定无向连通图, 定义两个点$s,t$个价值为切断一条边可以使$s,t$不连通的边数. 求最大价值. 显然只有桥会产生贡献. 先对边双连通分量缩点建树, 然后求直径即为答案. ...
分类:其他   时间:2019-07-12 13:20:56    收藏:0  评论:0  赞:0  阅读:18
【POJ2117】Electricity [tarjan 割点]
2117 -- Electricity 一个无向图 去掉一个点后最多能被分为多少个部分 输入要注意是n m同时为0才停.... n,m可能有一个为零 别问我为什么知道... 其实每太弄懂.....再看看吧 ...
分类:其他   时间:2019-07-11 11:35:13    收藏:0  评论:0  赞:0  阅读:25
欧拉回路与欧拉路径
什么叫颓,我是彻底明白了。 定义: 欧拉路径:在一个图中,由i点出发,将每个边遍历一次最终到达j点的一条路径。 欧拉回路:i=j时的欧拉路径。(也就是把所有边绕一边,最后回到自己)。 判断欧拉回路: 无向图:每个点的度数为偶数(两只手才能成环,一只手咋成环呢) 有向图:每个点的入度等于出度(一个出去 ...
分类:其他   时间:2019-07-09 14:25:43    收藏:0  评论:0  赞:0  阅读:28
P2863 [USACO06JAN]牛的舞会The Cow Prom
题面 这题确实是一个近乎(就是)tarjan板子的一道题,也是少有不用缩点的题目 把题目翻译一下吧,就是说若一头奶牛身上的绳子以顺时针方向出去,一直遍历下去可以回来,就说明能够完成圆舞,及若一群奶牛在同一强连通分量中,则可以完成圆舞,而又因为只能顺时针访问,故有向(我之前当成无向图做居然能拿90分? ...
分类:其他   时间:2019-07-09 12:47:59    收藏:0  评论:0  赞:0  阅读:23
【模板】割点(割顶)
题目背景 割点 割点 题目描述 给出一个n个点,m条边的无向图,求图的割点。 给出一个n个点,m条边的无向图,求图的割点。 输入格式 第一行输入n,m 下面mm行每行输入x,y表示x到y有一条边 第一行输入n,m 下面mm行每行输入x,y表示x到y有一条边 输出格式 第一行输出割点个数 第二行按照节 ...
分类:其他   时间:2019-07-08 23:54:02    收藏:0  评论:0  赞:0  阅读:39
贝壳找房魔法师顾问 2018 计蒜之道 复赛
https://nanti.jisuanke.com/t/A1725 V&V 无向图 强连通图 每个子图,n个点,选择n-1条,使互相连接 因为目标点x->点y,可以改为点y->点x V&C 弱连通图(将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向 ...
分类:其他   时间:2019-07-07 22:26:23    收藏:0  评论:0  赞:0  阅读:34
[欧拉回路][并查集] Bzoj P3706 反色刷
Description 给一张无向图,边有黑白两种颜色,现在你有一堆反色刷,可以从任意点开始刷,经过若干条边后回到起点。现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。因为某种原因,边的颜色是会改变的,于是。。需要支持以下操作:1 x 把第x条边反色(编号从0~m-1)2 询问当前图中最 ...
分类:其他   时间:2019-07-07 13:43:31    收藏:0  评论:0  赞:0  阅读:27
[欧拉回路][dfs] Uoj #117 欧拉回路
题目大意 给出一个n个点的有向图或无向图,要求输出其中一条欧拉回路 ( n<=100000 ) 给出一个n个点的有向图或无向图,要求输出其中一条欧拉回路 ( n<=100000 ) 题解 听说有个叫环套环的算法,好像实现有点复杂,身为蒟蒻,能水就水 发现有向图和无向图各占50分 我们先可以将每个点的 ...
分类:其他   时间:2019-07-06 20:36:43    收藏:0  评论:0  赞:0  阅读:42
2779条   1 2 3 4 ... 139 下一页
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号