HDU 4571 SPFA+DP-白红宇

HDU 4571 SPFA+DP

阅读量：4309 次

发布时间：2019-06-06

本文共 3084 字，大约阅读时间需要 10 分钟。

好题，长沙邀请赛的一道题。

这种题还是蛮常见的，SPFA+DP优化，记得上次北大校赛就有一道。

根据题意，我们可以虚拟两个超级源点和超级汇点，源点到所有点的距离都是这段距离加上参观的时间。所有点到汇点的距离就是该点到终点的距离。

这样控制之后，对于终点就有2个选择了，路过或者参观。

对于途中除起点终点以外的点，我们可以先进行一遍floyd，然后根据他们的val值进行连边，值是两点之间的距离加上参观的时间。这样对于每一点其实也有两个选择了，可以参观该点，即a -> b，也可以路过该点,即a -> b(路过，floyd保证了这一点) ->c。

然后从源点开始跑一遍spfa,最后在终点和超级汇点之间找到一个最大值，就是答案。

这道题期间犯了一个很2的错误，我已经不能多说了。

下面是代码：

#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define Max 2505#define FI first#define SE second#define ll long long#define PI acos(-1.0)#define inf 0x3fffffff#define LL(x) ( x << 1 )#define bug puts("here")#define PII pair
                
                 #define RR(x) ( x << 1 | 1 )#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;#define N 105#define M 20005#define K 305int tim[N] , val[N] ;int Map[N][N] ;int n , m , s , e , t ;struct kdq { int s , e, l ,next ;} ed[M] ;int head[N] , num ;void add(int s , int e ,int l) { ed[num].e = e ; ed[num].l = l ; ed[num].next = head[s] ; head[s] = num ++ ;}int vis[N][K] ;int dp[N][K] ;// dp[i][j]表示点i在时间j的时候的最大值PII qe[N * 1000] ;void init() { mem(head ,-1 ) ; num = 0 ; mem(val ,0) ; mem(tim ,0) ; for (int i = 0 ; i < N ; i ++ ) { for (int j = 0 ; j < N ; j ++ ) Map[i][j] = inf ; Map[i][i] = 0 ; } cin >> n >> m >> t >> s >> e ; for (int i = 0 ; i < n ; i ++ )scanf("%d",&tim[i]) ; for (int i = 0 ; i < n ; i ++ )scanf("%d",&val[i]) ; while(m -- ) { int x , y , z ; scanf("%d%d%d",&x,&y,&z) ; Map[x][y] = Map[y][x] = min(Map[x][y] , z) ; } for (int k = 0 ; k < n ; k ++ ) for (int i = 0 ; i < n ; i ++ ) for (int j = 0 ; j < n ; j ++ ) Map[i][j] = min(Map[i][j] , Map[i][k] + Map[k][j]) ; for (int i = 0 ; i < n ; i ++ ) { for (int j = i + 1 ; j < n ; j ++ ) { if(Map[i][j] != inf) { if(val[i] > val[j])//根据他的价值升序建边 add(j , i , Map[i][j] + tim[i]) ; else if(val[j] > val[i]) add(i , j , Map[i][j] + tim[j]) ; } } } add(n , s , tim[s]) ;//S -> i , i -> E 。 S = n ,E = n + 1 。 for (int i = 0 ; i < n ; i ++ ) { if(i != s && Map[i][s] != inf) { add(n , i , tim[i] + Map[s][i]) ; } if(i != e && Map[i][e] != inf) { add(i , n + 1 , Map[e][i]) ; } } for (int i = 0 ; i < N ; i ++ ) { for (int j = 0 ; j < K ; j ++ ) { dp[i][j] = 0 ; vis[i][j] = 0 ; } } vis[n][0] = 1 ; int hh = 0 , tt = 0 ; qe[hh ++ ] = mp(n , 0) ; while(hh > tt) { PII tp = qe[tt ++ ] ; int fk1 = tp.FI ; int fk2 = tp.SE ; vis[fk1][fk2] = 0 ; for (int i = head[fk1] ; ~i ; i = ed[i].next ) { int nxt = ed[i].e ; int l = ed[i].l + fk2 ; if(l > t)continue ; if(dp[nxt][l] < dp[fk1][fk2] + val[nxt]) { dp[nxt][l] = dp[fk1][fk2] + val[nxt] ; if(!vis[nxt][l]) { vis[nxt][l] = 0 ; qe[hh ++ ] = mp(nxt , l) ; } } } } int ans = 0 ; for (int i = 0 ; i <= t ; i ++ ) { ans = max(ans , dp[e][i]) ; ans = max(ans , dp[n + 1][i]) ; } printf("%d\n",ans) ;}int main() { int T ; cin >> T ; for (int i = 1 ; i <= T ; i ++ ) { printf("Case #%d:\n",i) ; init() ; } return 0 ;}

转载于:https://www.cnblogs.com/bbsno1/p/3271363.html

你可能感兴趣的文章