cf721 C DP

题目大意：给你个有向无环图，询问从1到n的路径里面，时间小于T的，但是路过点数是最多的路径。求点数

n，m只有5000，所以大胆一点，n^2的算法就冲上去。题目要什么我们的dp就设计什么。
设f[i][j]有两个权值v1,fa;
意义是从1走到i走过了j个点的最小权值。走到i点的前一个点是fa。
那么只要做一次拓扑排序，拓扑排序后就可以做一个线性的dp。不做拓扑会可能发现某个点还没被更新但是你就在利用这个点走下一个了。
这个dp怎么转移呢
就是从f[i][j]转移到f[to][j+1]就可以了，也就是枚举i的所有出边，计算权值就够了。
最后的答案就是在f[n][k]找到最大的k，逆序输出就好了（我们记录fa就是为了输出）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define ll long long
#define double long double
using namespace std;
#define PI
3.1415926535898
#define eqs 1e-10
const long long max_ = 5000 + 7;
int mod = 10000;
const int inf = 1e9;
const long long INF = 1e18;
int read() {
int s = 0, f = 1;
char ch = getchar();
while (ch<'0' || ch>'9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0'&&ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
inline int min(int a, int b) {
return a < b ? a : b;
}
inline int max(int a, int b) {
return a > b ? a : b;
}
int du[max_],head[max_],xiann = 2,n,m,T;
struct {
int next, to, value;
}xian[max_];
inline void add(int a, int b, int c) {
xian[xiann].next = head[a];
xian[xiann].to = b;
xian[xiann].value = c;
head[a] = xiann;
xiann++;
}
queue<int> que;
int tp[max_], tpn,ind[max_],flag;
void bfs() {
for (int i = 1; i <= n; i++) {
if (!du[i])que.push(i);
}
//que.push(1);
while (!que.empty()){
int tou = que.front(); que.pop();
if (flag || (!flag && tou == 1)) {
flag = 1;
tp[++tpn] = tou;
ind[tou] = tpn;
}
if (tou == n)return;
for (int i = head[tou]; i; i = xian[i].next) {
int to = xian[i].to;
du[to]--;
if (!du[to])que.push(to);
}
}
}
struct {
int val, fa;
}f[max_][max_];
void dfs(int now, int ned) {
if (now == 1) {
cout << "1 "; return;
}
dfs(f[now][ned].fa, ned - 1);
cout << tp[now] << " ";
}
signed main() {
n = read(), m = read(); T = read();
for (int i = 1; i <= m; i++) {
int a = read(), b = read(), c = read();
add(a, b, c);
du[b]++;
}
bfs();
memset(f, 127, sizeof(f));
f[1][1].fa = 1; f[1][1].val = 0;
for (register int i = 1; i <= tpn; i++) {
int now = tp[i];
for (register int z = head[now]; z; z = xian[z].next) {
int to = xian[z].to;
for (register int j = 1; j <= n; j++) {
if (f[i][j].val > inf)continue;
ll v = f[i][j].val + xian[z].value;
if (v <= T) {
if (f[ind[to]][j + 1].val > v) {
f[ind[to]][j + 1].val = v;
f[ind[to]][j + 1].fa = i;
}
}
}
}
}
for (register int i = n; i >= 1; i--) {
if (f[tpn][i].val <= inf) {
cout << i << endl;
dfs(tpn, i); return 0;
}
}
return 0;
}

最后

以上就是健忘蛋挞为你收集整理的cf721 C DP的全部内容，希望文章能够帮你解决cf721 C DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。