原题地址;http://poj.org/problem?id=3249 题意:给出n个点,m条边,每个点都提供了相对的点权值,然后给出相连着的边,问最大利润值。 思路:在拓扑排序的时候同步更新dp数组就行了. 注意:顶点权值可以取负就行了. #include <cmath> #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <q…

2018年8月1日 0条评论 0点热度 阅读全文

Frame Stacking Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 5165 Accepted: 1794 Description Consider the following 5 picture frames placed on an 9 x 8 array. ........ ........ ........ ........ .CCC.... EEEEEE.. ........ ........ ..BBBB.. .C.C...…

2016年7月20日 0条评论 0点热度 阅读全文

按照拓扑排序的顺序去扩展病毒数量,这样相当于所有节点只走了一遍就出了结果 #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef long long LL; const int mod=14…

2015年7月1日 0条评论 0点热度 阅读全文

Arbitrage Problem Description Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys …

2014年7月15日 0条评论 0点热度 阅读全文

Wormholes Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 29971   Accepted: 10844 Description While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar becau…

2014年7月14日 0条评论 0点热度 阅读全文

题目地址:hdu1102 多了一点花样,就是已经修过的路权值就是0了 代码: #include<iostream> #include<cstdio> #include<cmath> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; struct edge { int u; int v; int w; }; edge e[1000050]; in…

2014年4月28日 0条评论 0点热度 阅读全文

题目地址:你懂的 题干: 问题描述 很久以前,T王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。 为节省经费,T国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。 J是T国重要大臣,他巡查于各大城市之间,体察民情。所以,从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋,用于存放往来城市间的路费。 聪明的J发现,如果不在某个城市停下来修整,…

2014年3月22日 0条评论 0点热度 阅读全文

题目地址:hdu2544 就是直接求最短路  数据很弱  什么方法都可以 1 floyd  #include<iostream> using namespace std; #define INF 10000009 int d[105][105]; int n,m; void init() { for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=(i==j?0:INF); } // 1 floyd 2 Dijkstr…

2014年3月19日 0条评论 0点热度 阅读全文

题目地址: 某桥杯oj 题干: 问题描述 给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。 输入格式 第一行两个整数n, m。 接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。 输出格式 共n-1行,第i行表示1号点到i+1号点的最短路。 样例输入 3 3 1 2 -1 2 3 -1 3 1 2 样例输出 -1 -2 数据规模与约定 对于10%的数据,n = 2,m = 2。 对于30%的数据,n <= …

2014年3月18日 0条评论 0点热度 阅读全文

在学习这个算法之前,相信大家都已经学习过dijkstra算法了,如果大家还看过别的关于bellman-ford算法的文章,那些文章一定讲过dijkstra算法无法解决存在负权环的图的单源最短路问题。那么我们先来看看为什么dijkstra算法不行              如果我们采用dijkstra算法来求这个图的单源最短路径 经过四次松弛之后,我们认为最短路已经求出来了,其实不然。注意到图中存在2,3结点…

2013年5月5日 0条评论 0点热度 阅读全文