安全检查中...
请打开浏览器的javascript，然后刷新浏览器
< 浏览器安全检查中...
还剩 5 秒&HDU&&2544&最短路
int map[105][105];
int vis[105],dis[105];
const int INF=;
void init(int n)
for(i=1;i&=n;i++)
for(j=1;j&=n;j++)
map[i][j]=0;
map[i][j]=INF;
int dij(int st,int ed)
int i,j,id;
for(i=1;i&=n;i++)
dis[i]=map[1][i];
dis[st]=0;
vis[st]=1;
for(i=1;i&&/span&n;i++)
int mm=INF;
for(j=1;j&=n;j++)
if(!vis[j]&&dis[j]&=mm)
mm=dis[j];
vis[id]=1;
for(j=1;j&=n;j++)
if(dis[j]&dis[id]+map[id][j])
dis[j]=dis[id]+map[id][j];
return dis[n];
int main()
int st,ed,t;
while(~scanf("%d %d",&n,&m))
if(n==0&&m==0)
for(i=1;i&=m;i++)
scanf("%d %d %d",&st,&ed,&t);
if(t&&/span&map[st][ed])
map[st][ed]=map[ed][st]=t;
printf("%d\n",dij(1,n));
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。随笔分类 - ACM--图论
摘要: 题意 根据图中公式由A[]构造B[][]，现在给你B，问你存不存在一个数组A使之成立。 题解：对于每一位进行2-sat求解。 比赛半个小时时间，没做出来…… 一直T。 因为本身对算法不确定，所以也不知道怎么办 赛后才发现是数组开小了、、、、 真坑啊。。。
wenr 阅读(34) |
摘要: 题目就是给你一个图，图中部分边没有赋权值，要求你把无权的边赋值，使得s-&t的最短路为l。 卡了几周的题了，最后还是经群主大大指点……做出来的…… 思路就是跑最短路，然后改权值为最短路和L的差值，直到最短路为L，或者每条无权边都赋值为止。 点是0～n-1的，因为这个错了好几次= = dijkstra
wenr 阅读(20) |
摘要: 题意：John有n个牛棚，每个牛棚都住着一些牛，这些牛喜欢串门（drop around， 学到了。。。），所以John想要建几条路把他们连接起来。他选择的方法是建两个相连中转站，然后每个牛棚连接其中一个中转站就好啦。现在的问题是有一些牛相互憎恨，所以不能连同一个中转站，而又有一些牛相互喜欢，必须连同
wenr 阅读(111) |
摘要: 题意：有m扇门，每个门上有两把锁，打开任意一个锁都可以打开这扇门。门要按顺序一个一个打开。 现在有n对不同的钥匙，每对钥匙只能用其中一个，问最多能打开多少门。 题解：对钥匙建图，门是限制条件来建边。每加一扇门就多一个限制条件，直到2-sat不满足为止。当然二分会更快一些。有一个trick就是门上的两
wenr 阅读(99) |
摘要: 感觉这题比较裸，表现出了2-sat的本质。 不过构图我想的还是太简单了，a&b=1我只连了 a1-&b1,b1-&a1，但其实是不对的。这样连，a0和b0可以同时选到。应该连a0-&a1,b0-&b1这样就能保证a0,b0都不被选到。或运算同理。
wenr 阅读(16) |
摘要: 题面很邪恶啊。。。 一对新人请n-1对夫妻吃饭，人们坐在一张桌子的两侧，每一对互为夫妻关系的人必须坐在桌子的两侧。而且有些人两两之间会存在“通奸”关系，通奸关系不仅在男女之间，同性之间也有。新娘对面不可以座有通奸关系的人。判断是否存在可行的排座方案，存在的话输出和新娘同一排的人。 因为新娘对面不可以
wenr 阅读(40) |
摘要: 按字典序输出 直接dfs就好了（hdu1814（抄自 /kuangbin/archive//2712429.html） 输出任意一组解
wenr 阅读(181) |
摘要: #include const int N = 5005; const int M = 100010; struct Edge { int to, } edge[M]; int head[N]; int cntE; void addedge(int u, int v) { edge[cntE].to = edge[c...
wenr 阅读(33) |
摘要: 题意：有n个点，m条边，有重边。现在可以任意在图上添加一条边，求桥的最少数目。 题解：思路就是求出双连通分量之后缩点成为一棵树，然后求出树的直径，连接树的直径就能减少最多的桥。 难点在于：有！重！边！ 像我这样习惯于无脑用模板的人来说。。。。头疼死了。。。。。。 既然有重边，dfs的时候就不要标记点
wenr 阅读(18) |
摘要: 题意：有n*m的格子，每一个格子包含一个数字，0-9。你初始的能量为0，你可以玩k次，每一个你可以选择你现在的格子的正下方或者正右方的任意一个格子跳，但必须是之前没有跳过的格子。每玩一次你都可以跳任意次。每跳一次，从(x1, y1) 到 (x2, y2)，你将花费|x1-x2|+|y1-y2|-1的
wenr 阅读(14) |
摘要: 题目：My Brute Seaco是一个漂亮的妹子，喜欢玩一款名叫My Brute的游戏。情人节快到了，starvae和xingxing都想邀请妹子过节，但是妹子只能陪一个啊，于是两个人决定打一架，用男人的方式对决，来一场My Brute吧！ 一开始两个人都有n（n&100）只宠物，每个宠物有生命值
wenr 阅读(27) |
摘要: 比较简单的题了。 只需从左上角到右下角找两条路就可以了。 因为每个点只能走一次，所以拆点，限制流量为1。 因为求的是最大值，所以权值取反求最小值。 因为第一个点和最后一个点经过两次，只算一次，最后要减去。 ps：数组还是开大点好。。。。不知道什么时候就SB了。。。 注意汇点可能不是最后一个点（模板的
wenr 阅读(44) |
摘要: 因为每个点只能经过一次 所以考虑拆点 这题有坑，有重边。。 KM算法 把一个点拆成入点和出点 入点在X部，出点在Y步。 如果u，v之间有路径，就在X部的u点连接Y部的v点 求完美匹配。 当完美匹配的时候，每个点都有一个入度和一个出度，可知成环。 因为完美匹配求得是最大匹配 记得把每条边权值取相反数
wenr 阅读(44) |
摘要: 最简单的Ford-Fulkerson，复杂度O(FE) （F是最大流量，E是边数 每次从源点到汇点dfs寻找增广路。 const int MAXV = 2005; const int INF = 1&&30; struct Edge{ int to, cap, }; std::vector
wenr 阅读(58) |
摘要: 准备开始学习最大流。模板是在网上抄的，感觉这个看起来比较优雅。http://blog.csdn.net/d/article/details/8424820 持续更新。 （hdu zoj poj vj 都挂了 还怎么刷题啊……） （ sgu326. Perspecti
wenr 阅读(44) |
摘要: Bellman-Ford可以求有负权的图的最短路，也可以判断是否有负环存在。 单源最短路模板 如果没有环，最多更新n-1次，n是点的个数，如果更新了n次，证明图中有环。因为求的是最短路，所以一般判断的是负环，正环也可以判断的。 poj3259 Wormholes 求是否存在负环 #include &
wenr 阅读(15) |
摘要: 二分图的最小顶点覆盖：用最少的点，让每条边都至少和其中一个点关联。 最大匹配数 = 最小点覆盖数（Konig 定理） 水题…… 突然发现我以前的匈牙利算法模版有问题……因为这里左边的点时1~n,右边的点是1～m，所以有不同的点标号是相同的，注意注意！ 因为这个算法本身是O(n^2)的，所以数据必然不
wenr 阅读(44) |
摘要: 题意：给一个无向图n个点1~n，m条边，sigma(i*zi)%(1e9+7)。zi是这个图删掉i点之后的价值。一个图的价值是所有连通子图的价值之和，连通图的价值是每个点的乘积。 题解：讲道理这题不算难。注意一点就是一开始给的图不一定是连通的。然后就是割点会把一个连通图分成两个连通图，而其他点不影响
wenr 阅读(27) |
摘要: /wenruo/p/5264235.html KM算法用来求二分图最大权完美匹配。 本文配合该博文服用更佳：趣写算法系列之--匈牙利算法 本文没有给出KM算法的原理，只是模拟了一遍算法的过程。另，博主水平较差，发现问题欢迎指出，谢谢！！！！ 现在有N男N女
wenr 阅读(8120) |
摘要: 首先是二分图定义与判断 /wenruo/p/5243034.html 给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不连接同一个顶点，则称M是一个匹配。 一个很好的比喻是，一个二分图，左边代表男生，右边代表女生，连线代表有好感，匹配就
wenr 阅读(157) |
摘要: 二分图又称二部图。 二分图是无向图。 设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。 例如这就是一个二分图。 大概就是把顶点分成两堆，每堆内部没有边。 无向图G为二分图的充分必要条件是，G至少有两个顶点, 且其所有回路的长度均为
wenr 阅读(429) |
摘要: 最大流求混合图是否存在欧拉回路。 以下内容摘自/Missa/archive//2803107.html 讲的很清楚。 代码：
wenr 阅读(25) |
摘要: 最大流模板题 大部分Edmond-Karp算法代码都是邻接矩阵实现，试着改成了邻接表。 另附邻接矩阵版
wenr 阅读(33) |
摘要: 题意： 有m个猪圈 每个猪圈有不同数量的猪 [0, 1000]有n个顾客 每个顾客需要Bi头猪 有Ai个钥匙 能打开Ai个不同的猪圈顾客按顺序来买猪 只能买他有钥匙的猪 买完之后 这几个猪圈的猪可以相互转移 很神奇的题，建图简直太神奇~~ 建图： 每个顾客和源点的流量为与该顾客的相连的猪圈且该猪圈之
wenr 阅读(25) |
摘要: 一个公园中有 n 个景点，景点之间通过无向的道路来连接，如果至少两个环公用一条路，路上的游客就会发生冲突；如果一条路不属于任何的环，这条路就没必要修 问，有多少路不必修，有多少路会发生冲突 每一个连通块中，如果边数大于点数，这个块中所有的边全部是冲突边。 所有桥为不需要修建的路。 通过这题学习点的双
wenr 阅读(102) |
摘要: 做这题简直是一种折磨。。。 有n个骑士，骑士之间相互憎恨。给出骑士的相互憎恨的关系。 骑士要去开会，围成一圈坐，相互憎恨的骑士不能相邻。开会骑士的个数不能小于三个人。求有多少个骑士不能开会。 注意：会议可以开无数次，也就是说一个骑士其实是可以开多次会议的，所以一共可以开会的人也未必是奇数。 求出相互
wenr 阅读(83) |
摘要: 给定一个图，并给定边，a b c（c==1||c==2） 表示ab之间有c条边 求把尽可能多的有向边定向变成强联通图。 先把图当做无向图，加边时记录是否有边，dfs的时候不要把本没有的边用到！因为这个错了好多次。。。。然后就简单了，记录桥就可以了。
wenr 阅读(38) |
摘要: 给一个无向图，要求变成强连通的有向图，需要保留哪些边。 边的双连通，对于桥保留两条边，其他的只保留一条边。求双连通的过程中记录保留边。
wenr 阅读(27) |
摘要: 崇拜有传递性。求所有牛都崇拜的牛tarjan算法求强连通。 如果不连通就不存在。如果联通，缩点后唯一一个出度为零的点就是***，有多个则不存在。
wenr 阅读(23) |
摘要: 有n个牧场，Bessie 要从一个牧场到另一个牧场，要求至少要有2条独立的路可以走。现已有m条路，求至少要新建多少条路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指：没有公共边的路，但可以经过同一个中间顶点。 一个连通无向图最少加几条边变成双连通图(缩点后叶子节点（即度数为1）的个数 +
wenr 阅读(35) |
摘要: /wenruo/p/4989425.html 强连通 强连通是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径。 dfs遍历一个图，会生成一颗树。每个节点按最先遍历的时间给定一个编号，用一个数组dfn表示，又叫时间戳。 然后有几个概
wenr 阅读(59) |
摘要: vector建图被卡了。。改为链式前向星500ms过的。。差了四倍多？。。。 表示不太会用链表建图啊。。自己试着写的，没看模板。。嗯。。果然错了。。落了一句话orz 树的重心就是找到一个树中一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。
wenr 阅读(33) |
摘要: /wenruo/p/4959509.html 给一个图（不一定是连通图，无重边和自环），求练成一个长度为奇数的环最小需要加几条边，和加最少边的方案数。 很容易知道连的边数只能是0,1,2,3。 如果是二分图一定不含长度为奇数的环。 难点是如果是二分图怎么求
wenr 阅读(85) |
摘要: 裸最小生成树。用kauskal做方便一些。不得不说这么大数据用cin cout 真是作死。。活该T那么多次。。。/*************************************************Problem: 1751 User: G_loryMemory: 4640K Ti...
wenr 阅读(37) |
摘要: 火星人的血缘关系很奇怪，一个人可以有很多父亲，当然一个人也可以有很多孩子。有些时候分不清辈分会产生一些尴尬。所以写个程序来让n个人排序，长辈排在晚辈前面。输入：N 代表n个人 1~n 接下来n行 第i行表示第i个人的孩纸，无序排列，可能为空。0代表一行输入结束。（大概我的智商真的不合适，否则怎么这么...
wenr 阅读(44) |
摘要: 读题比做题难系列……poj1087输入n，代表插座个数，接下来分别输入n个插座，字母表示。把插座看做最大流源点，连接到一个点做最大源点，流量为1。输入m，代表电器个数，接下来分别输入m个电器，字符串表示。把电器看做最大流终点，连接到一个点做最大汇点，流量为1。输入k，代表转换器个数，接下来分别输入k...
wenr 阅读(22) |
摘要: 裸最大流，做模板用 m条边，n个点，求最大流
wenr 阅读(24) |
摘要: 很多图论的算法都有一个函数struct Edge {} edge[N * 2];int cnt_edge = 0;void add_edge(int from, int to, int w){ edge[cnt_edge].t...
wenr 阅读(42) |
摘要: 问题：牛要跨过一些障碍，希望以最小的体力跨过障碍，并且对于一条路径，只在乎其中最高的障碍。输入N代表站点数，标记为1--N，输入M代表路径数，从站点S到E之间需要跨过高度为H的障碍。输入T代表牛要完成的任务数。对于每个任务，输入A，B，输出一条从站点A到B的路径，使需要跨过的最高障碍为最低。代码：（F...
wenr 阅读(31) |
摘要: 最小生成树模板（嗯……在kuangbin模板里面抄的……）最小生成树(prim)/** Prim求MST * 耗费矩阵cost[][]，标号从0开始，0~n-1 * 返回最小生成树的权值，返回-1表示原图不连通 */const int INF = 0x3f3f3f3f;const int MA...
wenr 阅读(23) |
摘要: Description现在给出N个城市，城市之间共有M条道路。道路表示的方法是，代表从编号为u的城市，到标号为v的城市有条花费为w的道路。现在我们从编号为S的城市出发，目的地是编号为T的城市。但是我们在旅途中从u号城市到v号城市花费不只是他们的道路的花费w，还要加上以前的所有花费的一半，向下取整。I...
wenr 阅读(23) |
摘要: 最短路最基础的题啦，刚学会拿来练习~~~ 用的Dijkstra算法【目前就会这一个Orz#include #include #includeconst int MAX = 105;const int INF = 0x7int mp[MAX][M...
wenr 阅读(26) |