原题地址
http://codeup.hustoj.com/problem.php?cid=100000624&pid=0
解题思路
本来套了一下模板，然后一直是答案错误。 参考本篇博文： https://blog.csdn.net/qq_33375598/article/details/104439436 发现似乎是要加一步，即确定源点是哪一个。 方法即为遍历ve数组，ve[i]=0时i即为源点。 所以不能再判断e是否等于l之后直接输出关键路径，而应另外开一个数组存储路径~ 参考代码有借鉴上面那篇博文的部分qwq
参考代码
#include <bits/stdc++.h>
using namespace std
;
#define pb push_back
const int maxn
= 30;
struct node
{
int v
, w
;
};
int x
;
int inDegree
[maxn
], ve
[maxn
], vl
[maxn
];
vector
<node
> G
[maxn
];
stack
<int> topOrder
;
vector
<int> ans
[maxn
];
bool tpSortPath() {
queue
<int> q
;
int num
= 0;
for (int i
= 0; i
< x
; i
++) {
if (!inDegree
[i
]) q
.push(i
);
}
while (!q
.empty()) {
int v
= q
.front();
q
.pop();
num
++;
topOrder
.push(v
);
for (int i
= 0; i
< G
[v
].size(); i
++) {
int w
= G
[v
][i
].w
;
int v1
= G
[v
][i
].v
;
if (--inDegree
[v1
] == 0) q
.push(v1
);
if (ve
[v
] + w
> ve
[v1
]) {
ve
[v1
] = ve
[v
] + w
;
}
}
}
if (num
== x
) return true;
else return false;
}
int criticalPath() {
fill(ve
, ve
+ maxn
, 0);
if (!tpSortPath()) return -1;
int maxLength
= 0;
for (int i
= 0; i
< x
; i
++) {
if (ve
[i
] > maxLength
)
maxLength
= ve
[i
];
}
fill(vl
, vl
+ maxn
, maxLength
);
int u
, v
, w
;
while (!topOrder
.empty()) {
u
= topOrder
.top();
topOrder
.pop();
for (int i
= 0; i
< G
[u
].size(); i
++) {
v
= G
[u
][i
].v
;
w
= G
[u
][i
].w
;
if (vl
[v
] - w
< vl
[u
]) {
vl
[u
] = vl
[v
] - w
;
}
}
}
vector
<int> ans
[maxn
];
for (int u
= 0; u
< x
; u
++) {
for (int i
= 0; i
< G
[u
].size(); i
++) {
v
= G
[u
][i
].v
;
w
= G
[u
][i
].w
;
int e
= ve
[u
];
int l
= vl
[v
] - w
;
if (e
== l
)
ans
[u
].pb(v
);
}
}
int s
;
for (int i
= 0; i
< x
; i
++) {
if (ve
[i
] == 0) {
s
= i
;
break;
}
}
while (ans
[s
].size()) {
printf("(%c,%c) ", s
+ 'a', ans
[s
][0] + 'a');
s
= ans
[s
][0];
}
return maxLength
;
}
int main() {
int n
, y
, w
;
char a
, b
;
string nu
;
cin
>> n
;
while (n
--) {
scanf("%d%d", &x
, &y
);
char str
[maxn
];
scanf("%s", str
);
for (int i
= 0; i
< maxn
; i
++) G
[i
].clear();
fill(inDegree
, inDegree
+ maxn
, 0);
while (y
--) {
scanf("%*c%c %c %d", &a
, &b
, &w
);
int v1
= a
- 'a';
int v2
= b
- 'a';
G
[v1
].pb(node
{v2
, w
});
inDegree
[v2
]++;
}
int ans
= criticalPath();
printf("%d\n", ans
);
}
}
