• bool tupo_sort()//拓扑排序 求最长路径 { stack<int> s; for(int i=0;i;i++) { if(d[i]==0)s.push(i); } int cnt=0;//用于判断是否有环 while(!s.empty()) { int m=s.top(); cnt++;s.pop(); for(int i...

06-4. How Long Does It Take (25)

时间限制

200 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

CHEN, Yue

Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers N (<=100), the number of activity check points (hence it is assumed that the check points are numbered from 0 to N-1), and M, the number of activities. Then
M lines follow, each gives the description of an activity. For the i-th activity, three non-negative numbers are given: S[i], E[i], and L[i], where S[i] is the index of the starting check point, E[i] of the ending check point, and L[i] the lasting time of
the activity. The numbers in a line are separated by a space.

Output Specification:

For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output "Impossible".
Sample Input 1:
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4

Sample Output 1:
18

Sample Input 2:
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5

Sample Output 2:
Impossible

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
#define lson rt<<1,l,MID
#define rson rt<<1|1,MID+1,r
//#define lson root<<1
//#define rson root<<1|1
#define MID ((l+r)>>1)
typedef long long ll;
typedef pair<int,int> P;
const int maxn=3005;
const int base=1000;
const int inf=9999999999;
const double eps=1e-5;
int n,m;
struct node
{
int to,cost;
};
vector<node> G[maxn];//邻接表
int d[maxn];
int earlist[maxn];//活动最早结束的数组
bool tupo_sort()//拓扑排序 求最长的路径
{
stack<int> s;
for(int i=0;i<n;i++)
{
if(d[i]==0)s.push(i);
}
int cnt=0;//用于判断是否有环
while(!s.empty())
{
int m=s.top();
cnt++;s.pop();
for(int i=0;i<G[m].size();i++)
{
node tmp=G[m][i];
if(--d[tmp.to]==0)s.push(tmp.to);
if(earlist[m]+tmp.cost>earlist[tmp.to])//计算最长的路径
{
earlist[tmp.to]=earlist[m]+tmp.cost;
}
}
}
if(cnt<n)return false;//判断是否有环
return true;
}
int main()
{
int i,j,k,t;
cin>>n>>m;
for(i=0;i<m;i++)
{
node e;
int s;
cin>>s>>e.to>>e.cost;
G[s].push_back(e);
d[e.to]++;
}
if(tupo_sort())
printf("%d\n",*max_element(earlist,earlist+n));//输出earlist数组的最大元素
else
puts("Impossible");

return 0;
}




展开全文
• 题意：设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i...思路：拓扑排序求DAG最长路模板 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, h...
题意：设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i < j。设w（i，j）为边的长度，请设计算法，计算图G中<1，n>间的最长路径。

思路：拓扑排序求DAG最长路模板

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, h[N], cnt, ind[N], dis[N], inq[N];
struct node {
int v, w, net;
} no[N << 1];
void add(int u, int v, int w) {
no[cnt].v = v;
no[cnt].w = w;
no[cnt].net = h[u];
h[u] = cnt++;
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
for(int a, b, v, i = 0; i < m; i++) {
cin >> a >> b >> v;
}
dis[n] = -1, inq[1] = 1;
queue<int> q;
for(int i = 1; i <= n; i++)
if(!ind[i])
q.push(i);
while(!q.empty()) {
int j = q.front();
q.pop();
for(int i = h[j]; ~i ; i = no[i].net) {
int v = no[i].v;
ind[v]--;
if(inq[j]) {//保证前面边和起始点联通
dis[v] = max(dis[v], dis[j] + no[i].w);
inq[v] = 1;
}
if(!ind[v])
q.push(v);
}
}
cout << dis[n];
return 0;
}



展开全文
• 拓扑排序： 作用：判断有向图是否有环 做法：1在有向图中选取一个没有前驱（没有弧头指向的）的顶点且输出之 2从图中删除该顶点和所有以他为尾的弧 时间复杂度：O(n+e) n为顶点数，e为边数 关键路径路径长度最长...
拓扑排序：
作用：判断有向图是否有环
做法：1：在有向图中选取一个没有前驱（没有弧头指向的）的顶点且输出之
2：从图中删除该顶点和所有以他为尾的弧
3：重复以上步骤，直到所有顶点已经输出，或者不存在没有前驱的顶点（此情况为有环）
时间复杂度：O(n+e)  n为顶点数，e为边数

关键路径：
路径长度最长的路径为关键路径 目的：辨别哪些是关键活动
为什么是最长是关键呢？依我愚见，因为关键子工程要花最多时间，就算其他子工程就算完工了也无用，还要等这些时间花得比较多的子工程。
最短路径
1：求某个源点到其余各个顶点的最短路径：DijKstra法，按路径长度递增的次序产生的路径，边的权值不能为负。时间复杂度O(n^2)
2：求各个顶点间的最短路径，Floyd法，允许边的权值为负，，但是不允许在有向回路中出现负值, 时间复杂度O(n^3)


展开全文
• 出所给的AOE−网的关键路径出所给的AOE-网的关键路径出所给的AOE−网的关键路径。 输入 若干行整数，第一行有2个数，分别为顶点数v和弧数a，接下来有a行，每一行有3个数，分别是该条弧所关联的两个顶点...
$描述$
$求出所给的AOE-网的关键路径。$
输入
若干行整数，第一行有2个数，分别为顶点数v和弧数a，接下来有a行，每一行有3个数，分别是该条弧所关联的两个顶点编号和弧的权值
输出
若干个空格隔开的顶点构成的序列(用小写字母)
样例输入
9 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 3
样例输出
v1 v2 v5 v7 v9
思路：
拓扑排序 + dp
这是个有向图，我们可以在拓扑排序的过程中记录最大值，同时记录更新路径。
$AC \ Code:$
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
const int N = 1e5 + 1000;
#define ll long long
struct Edge
{
int next;
int to;
int dis;
}edge[N*2];
int deg[N];
inline void add(int from,int to,int dis){
edge[tot].to = to;
edge[tot].dis = dis;
deg[to] ++;
}
int a[10000];//记录拓扑序
int cnt = 0;
int f[10000];//f[i] 代表到 i的最大值
int pre[N];
void topsort(int n){
queue<int> Q;
for(int i = 1;i <= n;++i) if(!deg[i]) Q.push(i);
while(Q.size()){
int x = Q.front();
Q.pop();
a[++cnt] = x;
for(int i = head[x];~i;i = edge[i].next){
int y = edge[i].to;
int dis = edge[i].dis;
if(f[y] < f[x] + dis) f[y] = f[x] + dis,pre[y] = x;
if(--deg[y] == 0) Q.push(y);
}
}
}
inline void init(){
tot = 0;
}
void print(int x){
if(pre[x] == 0) {
cout<<'v'<<x<<' ';
return ;
} ;
print(pre[x]);
cout<<'v'<<x<<' ';
}
int main(){
int n,m;
init();
cin>>n>>m;
for(int i = 1;i <= m;++i){
int u,v,dis;
cin>> u >> v >> dis;
}
topsort(n);
int M = 0;
for(int i = 1;i <= n;++i){
M = max(M,f[i]);
}
print(n);
}

$spfa求最长路$
$AC\ Code:$
#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#include<cstdio>
#include<sstream>
#include<vector>
#include<bitset>
#include<algorithm>

using namespace std;
#define gc(x)  scanf(" %c",&x);
#define mmt(x,y)  memset(x,y,sizeof x)
#define write(x) printf("%d\n",x)
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define ll long long
const ll mod =   1000000007;
const int N = 100000 + 100;
const int M = 3e6 + 1005;
int d[2000];
int vis[2000];
struct Edge
{
int next;
int to;
int dis;
}edge[N];
inline void add(int from,int to,int dis)
{
edge[tot].to = to;
edge[tot].dis = dis;
}
int pre[2000];
void spfa(int u)
{
mmt(d,0xcf);
mmt(vis,0);
d[u] = 0;
vis[u] = 1;
queue<int> Q;
Q.push(u);
while(Q.size()){
int x = Q.front();
Q.pop();
vis[x] = 0;
for(int i = head[x];~i;i = edge[i].next){
int y = edge[i].to;
int dis = edge[i].dis;
if(d[y] < d[x] + dis){
d[y] = d[x] + dis;
pre[y] = x;
if(!vis[y]){
vis[y] = 1;
Q.push(y);
}
}
}
}
}
void print(int x)
{
if(pre[x] == 0) {cout<<'v'<<x<<' ';return ;}
print(pre[x]);

cout<<'v'<<x<<' ';
}
int main()
{
int n,m;
cin>>n>>m;
int u,v,dis;
for(int i = 1;i <= m;++i){
cin>>u>>v>>dis;
}
spfa(1);
print(n);

}



展开全文
• 题目：3249–Test for Job 思路：题目给出了每个城市的权值w[i],同时保证了数据m行每行包含两个整数x，...这是一个有向无环图，因此我们可以先进行拓扑排序，然后在拓扑序顺序上对每个点进行松弛操作求最长路，由于要求
• 一、创建有向无环图：  我用的数据存储结构是邻接... 官方解释是：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)
• 给定一张带点权的DAG 一条入度为0节点到出度为0节点的最长路 把点权转化为边权（同时多源转化...先进行拓扑排序，再最长路径（利用DAG分层的性质可以在线性时间内出最长路） 1 #include <iostrea...
• 题意 给出一个有n个结点，m条边的DAG图，每个点都有权值，每条路径（注意不是边...这是在一个无起点、终点的图中的最长路的问题，因此无法像一般的最长路问题那样求解。 首先，因为图中只存在点权，为了方便，...
• 这个算是关键路径的模版题目了，解这个题目之前，首先说下关键路径的含义，传送门（度娘），个人的见解是，关键路径就是木桶的短板问题，比如有一群人约好去某个地方，大家从同一...以下是代码，相当于在拓扑排序
• 给定一个有向无环加权图，图中的最长路径。 该图中的最长距离为14，即2->4->6->2。 2.问题解决 首先我们要对有向无环加权图进行拓扑排序拓扑排序的意思简要来说就是将图中顶点和边排成一个线性序列，...
• 不容易啊不容易 搞了够四个...然后拓扑排序判环；然后树的直径并在此过程中记录路径，然后遍历度数 看度数>1的点是不是都在这条路上（大佬的做法：直接树的直径，因为权值都是1，树的直径+1等于点的个数，...
• 题目简述：先tarjan缩点，再从入度为零处进行一次拓扑排序，求最长路即可，话说拓扑排序求最长路真方便。。。 注意：　要明确拓扑的写法，用栈写最优。 　再进行拓扑排序之前我们要进行将点权转...
• 关键路径：广域网成整个工程所需的时间取决于从源点到汇点的最长路径长度。路径长度等于路径上各边的权之和。这条具有最大长度的路径就叫做关键路径(拓扑排序可以判断有向图是否有环)（并查集可以判断无向图是否有...
• 题目：有n 个长为m+1 的字符串，如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配，则两个字符串可以联接，问这n 个字符串最多...然后针对建好的图，进行拓扑排序，并检查是否有环，如果有环，直接返回fal...
• 题意：将一个字符串上的n个字符视作点，给出m条有向边，图中路径最长出现的相同字母数。 分析：首先如果这张图中有环，则可以取无限大的字符数，在求拓扑排序的同时可以确定是否存在环。 之后在拓扑排序的结果...
• 给定一个 $$n$$ 点 $$m$$ 边的边权非负的有向图，边有字符，以每个点为开头的最长路字典序最小的路径 $$hash$$ 值。 $$n,m\leq 10^6$$ 分析 首先建反图拓扑排序后入度不为0的点的答案为 $$inf$$ 。 在 $$dep$$ ...
• 一张有向无环图，以每个点为终点的最长路径。 解题思路 先拓扑排序，然后dpdpdp fy=max{fx+1}(x−&gt;y)f_y=max\{f_x+1\}(x-&gt;y)fy​=max{fx​+1}(x−>y) codecodecode #inclu...
• 这题与以前一个求最长路径的题差不多，这里定义状态dp[i][j]表示从某点开始跑到节点i时路径上出现字母j+'a'的最大次数。 只需要按照拓扑序跑一遍dp即可， ch[v] != j, dp[v][j] = max(dp[v][j], dp[u][j]); ch[v] !=...
• 请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。 思路： 首先我们加一个超级源S和一个超级汇T，然后整个题目就变成了$$S->T$$的最长链。计算出S到每一个点的最长路和每一个点到T的最长路，这样我们...
• 请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。 2,1 DAG可能有多个起点和终点，所以不妨建S点和T点作为所有点的起点和终点，这样整个图中的最长路就是S到T的最长路。接下来考虑如何动态维护即可。 ...
• 两条最短路的 最长公共路径 一定是若干条连续的边， 并且满足拓扑序。 于是我们分别 正向 和反向走第二条路径，若该条边同时是两条最短路径上的边， 则加入边集。 最后拓扑 最长链即可 Code 1 #include&...
• 题意明确两个人的最短路最长公共路径 1.所求是一段链，若答案不是连续路径，则两人会有再次相遇的情况，若有再次相遇则对另一方就不是最短路； 2.我们要求最长公共路径，就对每一个点跑最短路，也就是跑4遍，再...
• 1、ve数组的求解 ve：顶点（事件）的最早开始...//拓扑排序，顺便ve数组 bool topologicalSort() { queue<int> q; for(int i=0;i<n;i++) //遍历所有点，将入度为0的点加入队列 { if(inDegree[...
• 我觉得麻烦，类比dijkstra求最短路，用的递归求最长路。 注意，存在多个源点，所以这里添加一个 超级总源点N。 对于存在环的情况，还是用了拓扑排序判断的。 已AC. 3. 源码： #include #include #