CodeForces - 721C 拓扑排序+dp

题意：

n个点m条边的图，起点为1，终点为n，每一条单向边输入格式为：

a,b,c //从a点到b点耗时为c

题目问你最多从起点1到终点n能经过多少个不同的点，且总耗时小于等于t

题解：

这道题我原本以为是改一下最短路去做，，，但是想不到怎么写。网上搜了搜，发现是拓扑+dp。

拓扑排序有啥用？

比如一共有好多件事情，事情A要再事情B（或者更多）事情做完才能做，也就是给你了一种完成事件的顺序

那么转化到这道题上就是从1点到其他点有多种方式，它就是按顺序做这些事情（也就是按这个顺序dp）

那么我看了网上代码后发现，他们都是把1这个点当于没有入度去处理，也就是数据默认1这个点的入度为0

譬如下面这个数据用在本题代码上就不行：

但是实际画图你会发现1->3->4这条路是可以的

回归本题dp：

dp[i][j],到达i点时，观光了j个景点的最小时间
转移是这样对于一条边u -> v,dp[v][j] = min(dp[v][j],dp[u][j - 1] + dis[u][v]);

代码：

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <math.h>

 5 #include <string.h>

 6 #include <queue>

 7 #include <set>

 8 #include <map>

 9 #include <algorithm>

10 using namespace std;

11 const int maxn=5005;

12 const int inf=0x3f3f3f3f;

13 int vin[maxn];

14 struct edge

15 {

16     int v;

17     int cost;

18     edge(int a,int b)

19     {

20         v=a,cost=b;

21     }

22 };

23 typedef vector<edge> vec;

24 vec e[maxn];

25 int n,m,t;

26 struct node

27 {

28     int per;

29     int use;

30 } dp[maxn][maxn];

31 void tp()

32 {

33     queue<int>q;

34     for(int i=1; i<=n; i++)

35         if(vin[i]==0)

36             q.push(i);

37     while(!q.empty())

38     {

39         int u=q.front();

40         q.pop();

41         for(int i=0; i<e[u].size(); i++)

42         {

43             int v=e[u][i].v;

44             int cost=e[u][i].cost;

45             vin[v]--;

46             if(vin[v]==0)

47                 q.push(v);

48             for(int j=1; j<=n; j++)

49                 if(dp[v][j].use>dp[u][j-1].use+cost)

50                 {

51                     dp[v][j].use=dp[u][j-1].use+cost;

52                     dp[v][j].per=u;

53                 }

54         }

55     }

56 }

57 void show(int i,int j)

58 {

59     if(dp[i][j].per==-1)

60     {

61         printf("1 ");

62         return;

63     }

64     show(dp[i][j].per,j-1);

65     printf("%d ",i);

66 }

67 int main()

68 {

69     cin>>n>>m>>t;

70     int a,b,c;

71     for(int i=0; i<=n; i++)

72         for(int j=0; j<=n; j++)

73         {

74             dp[i][j].use=inf;

75         }

76     memset(vin,0,sizeof(vin));

77     for(int i=0; i<m; i++)

78     {

79         scanf("%d%d%d",&a,&b,&c);

80         e[a].push_back(edge(b,c));

81         vin[b]++;

82     }

83     dp[1][1].use=0;

84     dp[1][1].per=-1;

85     tp();

86     for(int i=n; i>=1; i--)

87     {

88         if(dp[n][i].use<=t)

89         {

90             printf("%d\n",i);

91             show(n,i);

92             return 0;

93         }

94     }

95     return 0;

96 }

巴特西

CodeForces - 721C 拓扑排序+dp

最新文章

热门文章