PAT 1018

题目 ： Public Bike Management

分值 ： 30
难度 ： 难题
思路 ： 最短路径解决不了，因为多层条件第二层不是贪心的，所以只能DFS+回溯了。
坑点 ： 肯定是有很多的，但我没遇到，哈哈哈，我又用了递归倒叙打印。
评语 ： 以前一直觉得是难题，很怕这题，这次动手一做，一次就AC太爽了。哈哈哈。

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
using namespace std ;
#define  MAX_ 99999999
int Cmax , N ,Sp , M ;
int value[501] ;
int map[501][501] ;
int result[501] ;
int temp[501] ;
int flag[501] ;
int min_cost =MAX_ ;
int min_s_bike = MAX_ ;
int min_r_bike =MAX_ ;
int temp_cost ;
int temp_s_bike  ;
int temp_r_bike ;
void dfs(int start ,int target)
{
    if(start == target)
    {   //    距离短                   距离一样                   发出的bike少                        距离一样 且 送出的bike一样   但是回收的bike少
        if(temp_cost < min_cost || (temp_cost == min_cost)&&(temp_s_bike< min_s_bike) ||  ((temp_cost == min_cost)&&(temp_s_bike== min_s_bike))&& (temp_r_bike <  min_r_bike))
        {
            min_cost = temp_cost ;
            min_r_bike = temp_r_bike ;
            min_s_bike =temp_s_bike ;
            for(int i = 0 ; i< 501 ;i++) //更优解路径保存
            {
                result[i] = temp[i] ;
            }
        }
        return ;
    }
    for(int i = 1 ;i<= N ; i++)   //遍历start 开始可能的 出发点；
    {
        if(map[start][i] != MAX_  && !flag[i] && start != i )  //start-> i 存在通路  且 i没被访问过
        {
            int olds , oldr ,oldc;
            olds  =temp_s_bike;
            oldr = temp_r_bike ;
            oldc = temp_cost ;
            temp_cost += map[start][i] ;
            int fix = value[i] - Cmax/2 ;

            if(fix > 0 ) //就是说 i这个点富裕
                temp_r_bike += fix ;  //富裕的东西就要被带走
            else
            {
                temp_r_bike += fix ; //receive 够用 send 不用多
                if(temp_r_bike < 0)  // receive 不够用 send 多起来 且 receive 清零
                {
                    temp_s_bike -= temp_r_bike ;
                    temp_r_bike =0 ;
                }

            }
            flag[i] = 1 ;
            temp[i] = start;
            dfs(i , target) ; //通过i这个节点 往下 深搜
            flag[i] = 0 ;
            temp[i] = 0;
            temp_cost = oldc ;
            temp_s_bike =olds;
            temp_r_bike = oldr ;

        }
    }
    return ;

}
void print(int cur)
{
    if(cur!=0)
    {
        print(result[cur]) ;
        cout <<"->"<<cur ;
    }

}
int main() {
    cin >> Cmax >> N >>Sp >> M ;
    for(int i = 1; i <=N ; i++)
        cin>>value[i];
    for(int i = 0 ; i<=N ; i++)
        for(int j = 0 ; j<=N ; j++)
            if(i!=j)
                map[i][j] =MAX_ ;
    for(int i = 0 ; i< M ;i++)
    {
        int v1 ,v2 ,cost ;
        cin >>v1 >> v2 >>cost ;
        map[v1][v2] = cost ;
        map[v2][v1] = cost ;
    }
    dfs(0,Sp);
    cout<<min_s_bike <<" " ;
    int cur = Sp ;
    cout<<"0" ;
    print(Sp) ;
    cout <<" "<<min_r_bike <<endl;

}
}

第二次重做时的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>
#define Max_ 999999999
using namespace std;
vector<int> db ;
vector<int> ans;
vector<int> temp_ans ;
int Map[501][501];
int Cmax , N , Sp , M;
bool flag[501] ;
int min_dict =Max_ , mini_sent = Max_ , mini_back =Max_ ;
void Dfs(int pos , int target , int dict ,int sent_bike , int back_bike )
{
    if(pos==target)
    {
        if(dict < min_dict)
        {
            min_dict = dict ;
            mini_sent = sent_bike ;
            mini_back = back_bike ;
            ans = temp_ans;
        }
        else if(dict == min_dict ){
            if(sent_bike < mini_sent)
            {
                mini_sent = sent_bike ;
                mini_back = back_bike ;
                ans = temp_ans;
            }
            else if(sent_bike == mini_sent && back_bike < mini_back)
            {
                mini_sent = sent_bike ;
                mini_back = back_bike ;
                ans = temp_ans;
            }
        }
        return ;
    }
    for(int i = 1 ; i<= N ; i++)
    {
        if(flag[i] || Map[pos][i] == Max_ || pos == i ) continue ;
        temp_ans.push_back(i) ;
        flag[i] = true;
        int sent_ =sent_bike , back = back_bike +(db[i]-Cmax/2)  ;
        if( back < 0 )
        {
            sent_  -=( back_bike + (db[i]-Cmax/2) );
            back= 0 ;
        }
        Dfs(i , target ,dict+Map[pos][i] ,sent_ ,back);
        temp_ans.pop_back() ;
        flag[i] = false ;
    }
}
void init()
{
    for(int i = 0 ;i< 501 ;i++)
        for(int j= 0 ; j< 501;j++)
            if(i!=j)
                Map[i][j] = Max_ ;
}
int main()
{
    int t ,c1 ,c2 ;
    cin >> Cmax >> N >> Sp >> M ;
    db.resize(N+1);
    init();
    for(int i = 1 ; i<= N ; i++)
    {
        cin >> t ;
        db[i] = t ;
    }
    for(int i = 0 ; i< M ; i++)
    {
        cin >> c1 >> c2 >> t ;
        Map[c1][c2] = t ;
        Map[c2][c1] = t ;
    }
    Dfs( 0, Sp , 0 , 0, 0);
    cout <<mini_sent <<" 0" ;
    for(int i = 0 ;i < ans.size(); i++)
        cout <<"->"<<ans[i];
    cout <<" " <<mini_back<<endl ;
}