1018. Public Bike Management (30)

痛定思痛。 2022-05-31 09:17 159阅读 0赞

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in *perfect* condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

![11_lrrk0m5o4kg.jpg][]  
Figure 1

Figure 1 illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3, we have 2 different shortest paths:

1. PBMC -> S1 \-> S3. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1 and then take 5 bikes to S3, so that both stations will be in perfect conditions.

2. PBMC -> S2 \-> S3. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

**Input Specification:**

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax (<= 100), always an even number, is the maximum capacity of each station; N (<= 500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci (i=1,...N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers: Si, Sj, and Tij which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space.

**Output Specification:**

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0->S1\->...->Sp. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge's data guarantee that such a path is unique.

**Sample Input:**

10 3 3 5
    6 7 0
    0 1 1
    0 2 1
    0 3 3
    1 3 1
    2 3 1

**Sample Output:**

3 0->2->3 0

--------------------

题目大意：

杭州的共享单车服务，为世界各地的游客提供了极大的便利。一个人可以在任何一个站点租借一辆共享单车并可以将其停放在城市里的任何一个站点。  
共享单车管理中心（PBMC）时时监测所有站点的容量。如果一个站点处于半满状态，那么他就处于完美状态。如果一个站点是满的或是空的，共享单车管理中心将收集或发送共享单车来将站点调整到完美状态。而且，沿途所有的站点都将进行调整。  
当一个站点出问题时，共享单车管理中心总是选择最短路径到达该站点。如果存在不止一条最短路径，则选择从共享单车管理中心发出共享单车最少的一条。  
图一是一个事例。车站有顶点表示，道路与边相对应。边上的数值表示从一个站点到另一个站点所需要的时间。定点内的数字表示当前站点内存储的共享单车的数量。给定每个站点的最大容量是10.为了解决站点3的问题，我们有两条最短路径。：  
1.共享单车管理中心->S1->S3.在这种情况下，共享单车管理中心必须发送4辆共享单车，因为我们只能从站点1收集1辆共享单车但是我们需要发送5两共享单车到站点3，这样两个站点才能达到完美状态。  
2.共享单车管理中心->S2->S3。这个路径和路径1花费相同的时间，但是却只需要送共享单车管理中心发送三辆共享单车，因此这条路径经被选中。  
输入规范：  
每个输入文件包含一个测试案例。第一行包含4个数字：Cmax（<=100），总是一个偶数，代表每个站点的容量；N（<=500）,表示站点的总数；Sp,表示有问题的站点的下标（站点的标号从1到N，共享单车管理中心的标号是0）；M,代表路的数量，第二行包含N个非负数Ci(i=1,....N)每个Ci分别代表Si站点的共享单车的数量。接下来是M行，每行包含三个数字：Si,Sj和Tij,Tij代表从站点i到站点j需要花费的时间。所有的数字用一个空格隔开。  
输出规范：  
对于每个测试用例，在一行上打印出你的结果。第一个数字打印出共享单车管理中心需要发送的共享单车的数量。之后是一个空格，输出路径的格式为：0->S1->...->Sp.之后是一个空格，最后输出站点p调整到完美状态后我们需要送回共享单车管理中心的共享单车的数量。  
注意如果路径不是唯一的，输出需要送回的共享单车数量最小的路径。确保这样的路径是独一无二的。

代码：

#include<stdio.h>
    #include<algorithm>
    #include<vector>
    using namespace std;
    int map[501][501],station[501],visited[501];
    int curLen = 0;
    int minLen = 1<<30;
    int curBike = 0;
    int minBike = 1<<30;
    int curSend = 0;
    int minSend = 1<<30;
    int k,m,n;
    vector<int> curRoad;
    vector<int> minRoad;
    void DFS(int cur)
    {
       if(curLen>minLen)
    		return;
    	if(cur == k)
    	{
    		bool choosed = false;
    		if(curLen<minLen)
    		{
    			choosed = true;
    
    		}else if(curLen == minLen)
    		{
    			if(curSend<minSend)
    			{
    				choosed = true;
    			}else if(curSend == minSend)
    			{
    				if(curBike<minBike)
    				{
    					choosed = true;
    				}
    			}
    		}
    		if(choosed)
    		{
    			minLen =  curLen;
    			minSend = curSend;
    			minBike = curBike;
    			minRoad = curRoad;
    		}
    		return;
    	}
    	for(int i=0;i<=m;i++)
    	{
    		if(visited[i]==0 && map[cur][i]>0)
    		{
    			visited[i] = 1;
    			curLen+= map[cur][i];
    
    			int lastCurSend = curSend;
    			int lastCurBike = curBike;
    			if(station[i]+curBike<n/2){
    				curSend += n/2 - (station[i]+curBike);
    				curBike = 0;
    			}else{
    				curBike = station[i]+curBike-n/2;
    			}
    			curRoad.push_back(i);
    			DFS(i);
    			curRoad.pop_back();
    			curSend = lastCurSend;
    			curBike = lastCurBike;
    			curLen-= map[cur][i];
    			visited[i] = 0;
    		}
    	}
    }
    int main()
    {
        int i,j,t,x,y,p;
        scanf("%d %d %d %d",&n,&m,&k,&t);
        for(i=1;i<=m;i++)
        {
            scanf("%d",&station[i]);
        }
        for(i=0;i<t;i++)
        {
            scanf("%d %d %d",&x,&y,&p);
            map[x][y]=map[y][x]=p;
        }
        visited[0]=1;
        DFS(0);
        printf("%d ",minSend);
        printf("0");
        for(i=0;i<minRoad.size();i++)
        {
            printf("->%d",minRoad[i]);
        }
        printf(" %d",minBike);
        return 0;
    }

[11_lrrk0m5o4kg.jpg]: http://nos.patest.cn/11_lrrk0m5o4kg.jpg