首页 > 试题广场 >

Public Bike Management (30)

[编程题]Public Bike Management (30)
  • 热度指数：13906 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
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.

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.

输入描述:
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.


输出描述:
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.
示例1

输入

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

输出

3 0->2->3 0
算法知识视频讲解
添加回答
C/C++
OFShare头像 OFShare 
//dfs+回溯
#include <bits/stdc++.h>
using namespace std;
const int maxn=500+5,INF=1e9;
int cap,n,sp,m,bike[maxn],cost[maxn][maxn];
vector<int> G[maxn],anspath,curpath;
int minsend=INF,minback=INF,mincost=INF,vis[maxn];
void dfs(int cur,int cursend,int curback,int curcost){
    vis[cur]=1;curpath.push_back(cur);
    if(curcost>mincost) return ;
    if(cur==sp){
        if(curcost<mincost){
            mincost=curcost;minsend=cursend;minback=curback;
            anspath=curpath;return ;
        }if(curcost==mincost&&cursend<minsend){
            mincost=curcost;minsend=cursend;minback=curback;
            anspath=curpath;return ;        
        }if(curcost==mincost&&cursend==minsend&&curback<minback){
            mincost=curcost;minsend=cursend;minback=curback;
            anspath=curpath;return ;
        }
        return ;
    }
    for(int i=0;i<G[cur].size();++i){
        int v=G[cur][i];
        if(!vis[v]){
            if(bike[v]+curback<cap/2) dfs(v,cursend+cap/2-bike[v]-curback,0,curcost+cost[cur][v]);
            else dfs(v,cursend,curback+bike[v]-cap/2,curcost+cost[cur][v]);
            vis[v]=0;curpath.pop_back();            
        }
    }
//    vis[cur]=0;curpath.pop_back();    
}
int main(){
    scanf("%d %d %d %d",&cap,&n,&sp,&m);
    for(int i=1;i<=n;++i) scanf("%d",&bike[i]);
    for(int i=1,x,y,z;i<=m;++i){
        scanf("%d %d %d",&x,&y,&z);
        G[x].push_back(y);G[y].push_back(x);cost[x][y]=z;cost[y][x]=z;        
    }
    dfs(0,0,0,0);
    printf("%d ",minsend);
    for(int i=0;i<anspath.size();++i)
        if(i==0) printf("%d",anspath[i]);
        else printf("->%d",anspath[i]);    
    printf(" %d\n",minback);
    return 0;
} 

发表于 2018-03-01 21:13:19 回复(1)
C/C++
BlackCarDriver头像 BlackCarDriver
/*
第一次做甲级真题，做一道题花掉的时间足够参加两次比赛了，做完后认真总结，觉得不算难，原本的想法是拖车到了出事地点，最后沿途回去，所以最后多出来的车还可以放回沿途车站，后来才发现原来带来和带回的数量并非一定有个0,所以。。。。额
相信这个代码对我来说已经算优秀了。奉上。
*/

const int maxn = 510;
int cmax,N,sp,m;          //车站容量，车站数量，出事位置，道路位置
int tmap[500][510];        //各点间的距离
int station[maxn],vis[maxn];                        //各个车站的车数量，访问标签
int min_time=1E9, ans_have=1E9, ans_need=1E9;            //已知到达出事车站的最小时间 ,最小需要带的车， 最少带回来的车
vector<int>path;        //到达出事车站时经过的路径
vector<int>ans_path;    //符合答案要求的路径

//s:当前点，e需要到达的点, time当前时间 , tneed需要从基地带来的车， 需要带回去的车
void dfs(int s,int e,int time,int tneed,int thave) {
vis[s] = true;
path.push_back(s);
if(s!=0){
int need = (cmax/2) - station[s];
if(need > 0) {             //需要往此站放车
tneed += (thave<need? need-thave : 0);
thave -= (thave<need? thave : need);
} else    thave -= need;     //需要在此站搬走一些车
}
if(s==e) {
if( time<min_time || (time==min_time && tneed<ans_need) ) {  //更优解条件
min_time = time;
ans_path = path;
ans_need = tneed;
ans_have = thave;
}
} else {
for(int i=1; i<=N; i++) {
if(vis[i]==false && tmap[s][i]>0) {
int next_time = time + tmap[s][i];
if( next_time <= min_time) dfs(i,e,next_time,tneed,thave);  //如果到下一步的时间已经比已知最短时间长，直接排除
}
}
}
vis[s] = false;
path.pop_back();
}

int main() {
cin>>cmax>>N>>sp>>m;
memset(tmap,-1,sizeof(tmap));
for(int i=1; i<=N; i++) cin>>station[i];
for(int i=0; i<m; i++) {
int ta,tb,tc;
cin>>ta>>tb>>tc;
tmap[ta][tb] = tmap[tb][ta] = tc;
}
dfs(0,sp,0,0,0);
cout<<ans_need<<" 0";
for(int i=1; i<ans_path.size(); i++) cout<<"->"<<ans_path[i];
cout<<" "<<ans_have<<endl;
}
编辑于 2018-12-08 10:22:16 回复(0)
蓝豆豆头像 蓝豆豆 
智商有限，自己没有做出来，这个是某个大佬的答案，拿出来研讨一下
1.应该使用基于深度优先搜索的查找方法查找从起点到终点的路径，但是需要用到退层操作，使得后面这个结点能够再次被访问到
2.设置一个全局变量数组存放得到的最短路径、路径需要送出的车辆和收回的车辆，这条路径对应的最短时间。
3.通过在深度优先搜索中得到的新路径和前面的路径进行比较，如果是更优的路径那就用它来刷新最短路径的相关数据。
4.用邻接矩阵来存储图的数据，同时要注意存储的时候由于是无向图，需要把它存储成对称矩阵的形式。

package com.zju.algorithem.pat;

import java.util.ArrayList;
import java.util.Scanner;

public class PublicBikeManagement {
	private static int Cmax;
	private static int N;
	private static int Sp;
	private static int M;
	private static ArrayList<Integer> path = new ArrayList<Integer>();		//暂存当前路径，退层的时候移除退层的那个点
	public static ArrayList<Integer> result;								//暂存已经得到的一条最短路径
	private static int minTime = Integer.MAX_VALUE;							//暂存路径的行使时间
	private static int send;
	private static int collect;
	private static boolean[] visited;
	private static int []C;
	/**
	 * 
	 * @param from			前一个结点，用于在后面定位路径
	 * @param cur			当前深入的结点
	 * @param des			目的地，也就是目标结点
	 * @param adj			图的邻接矩阵
	 * @param time			当前寻找这条路径的累计时间
	 */
	public static void dfs(int from, int cur, int des, int [][]adj,int time){		//time是当前这条路径目前累计的行走时间
		visited[cur] = true;
		path.add(cur);
		time += adj[from][cur];
		if(cur == des){
			/**
			 * 遍历在ArrayList中存的这条路径
			 * 计算当前这条路的路程长度
			 * 计算需要从老家带出来几辆自行车
			 * 计算需要带回老家几辆自行车
			 */
			int s = 0, c = 0;
			for(int i = 1 ;i < path.size(); i++){		//注意要跳过起点开始
				int j = path.get(i);
				if(C[j] > Cmax / 2 ){
					c += (C[j] - Cmax / 2);
				}
				else if(C[j] < Cmax / 2){
					if(c > (Cmax / 2) - C[j]){
						c -= (Cmax / 2 - C[j]);
					}
					else{
						s += ((Cmax / 2) - C[j] - c);
						c = 0;
					}
				}
			}
			if(time == minTime){
				if(s < send || (s == send && c < collect)){
					minTime = time;
					result = new ArrayList<Integer>(path);
					send = s;
					collect = c;
				}
			}
			else if(time < minTime){
				minTime = time;
				result = new ArrayList<Integer>(path);
				send = s;
				collect = c;
			}
		}
		else{		//深度遍历
			for(int i = 0;i < N;i++){
				if(!visited[i] && adj[cur][i] != 0){
					dfs(cur, i, des, adj, time);
				}
			}
		}
		//退层操作
		path.remove(path.size() - 1);
		visited[cur] = false;
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Cmax = in.nextInt();	//每个站点最大容量
		N = in.nextInt();	//总站点数
		N = N + 1;
		Sp = in.nextInt();	//问题站点的下标
		M = in.nextInt();	//路的条数
		C = new int[N];
		int [][]adj = new int[N][N];
		visited = new boolean[N];
		for(int i = 1;i < N;i++){
			C[i] = in.nextInt();
		}
		int Si, Sj, Tij;
		for(int i = 0 ;i < M; i++){
			Si = in.nextInt();
			Sj = in.nextInt();
			Tij = in.nextInt();
			adj[Si][Sj] = Tij;
			adj[Sj][Si] = Tij;
		}
		dfs(0, 0, Sp, adj, 0);
		System.out.print(send+" ");
		for(int i = 0;i<result.size()-1;i++)
		System.out.print(result.get(i)+"->");
		System.out.print(result.get(result.size()-1)+" ");
		System.out.println(collect);
	}
}


发表于 2017-09-09 19:42:27 回复(1)
JacobGo！头像 JacobGo！ 
package go.jacob.day924;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

/**
 * [编程题]Public Bike Management (30)
 * 
 * @author Jacob
 * 
 *         注意点：自行车只能在去的路径上投放，回来的路上不能投放
 * 
 * 
 */
public class Demo1 {
    static int[] dist;// 存储到起点的距离
    static int[] bikes;
    static boolean[] visited;// 每个站点是否被访问过
    static ArrayList[] edgeTo;// 每个点的上一个节点(可能有多个)
    static int[][] map;// map存储所有的边

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cMax = sc.nextInt(), staNum = sc.nextInt();
        int proSta = sc.nextInt(), roadNum = sc.nextInt();
        bikes = new int[staNum + 1];// 编号从1到N
        dist = new int[staNum + 1];// 编号从1到N
        visited = new boolean[staNum + 1];
        edgeTo = new ArrayList[staNum + 1];
        for (int i = 1; i <= staNum; i++) {
            bikes[i] = sc.nextInt();
        }
        for (int i = 0; i <= staNum; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        map = new int[staNum + 1][staNum + 1];
        for (int i = 0; i <= staNum; i++) {
            for (int j = 0; j < staNum; j++) {
                if (i == j)
                    map[i][j] = 0;
                else
                    map[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < roadNum; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            map[a][b] = map[b][a] = sc.nextInt();
        }

        dijkstra(0, proSta, cMax, staNum);

        // 找到所有的路径
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> path = new ArrayList<Integer>();
        findPath(0, proSta, path, list);
        // 现在list中存放着左右路径，对所有路径的所需车辆数进行计算
        NeedBike[] needBike = new NeedBike[list.size()];
        for (int i = 0; i < list.size(); i++) {
            needBike[i] = calculateBike(list.get(i), cMax);
        }
        Arrays.sort(needBike, new Comparator<NeedBike>() {

            @Override
            public int compare(NeedBike o1, NeedBike o2) {
                if (o1.needBike != o2.needBike)
                    return o1.needBike - o2.needBike;
                else
                    return o1.backBike - o2.backBike;
            }
        });
        // 输出结果
        NeedBike res = needBike[0];
        System.out.print(res.needBike);

        ArrayList<Integer> road = res.road;
        System.out.print(" " + road.get(road.size() - 1));
        for (int i = road.size() - 2; i >= 0; i--) {
            System.out.print("->" + road.get(i));
        }
        System.out.print(" " + res.backBike);
    }

    /*
     * 路径是逆序的
     */
    private static NeedBike calculateBike(ArrayList<Integer> array, int cMax) {
        NeedBike res = new NeedBike();
        int needBike = 0, curBike = 0;
        int backBike = 0;
        // 因为array.get(array.size()-1)是主站，不需要自行车
        for (int i = array.size() - 2; i >= 0; i--) {
            // 车辆不够，需要从主站中获取
            if (bikes[array.get(i)] + curBike < cMax / 2) {
                needBike += cMax / 2 - bikes[array.get(i)] - curBike;
                curBike = 0;
            } else {// 车辆足够
                curBike = bikes[array.get(i)] + curBike - cMax / 2;
            }
            if (i == 0)
                backBike = curBike;
        }
        res.needBike = needBike;
        res.backBike = backBike;
        res.road = array;
        return res;
    }

    private static void findPath(int res, int proSta, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> list) {
        if (res == proSta) {
            path.add(res);
            list.add(new ArrayList<Integer>(path));
            path.remove(path.size() - 1);
            return;
        }

        ArrayList<Integer> pre = edgeTo[proSta];
        for (int a : pre) {
            path.add(proSta);
            findPath(res, a, path, list);
            path.remove(path.size() - 1);
        }
    }

    /*
     * dijkstra算法，找到最短路径（可能有多条） 所以用arrayList保存每个站点的上一个站
     */
    private static void dijkstra(int res, int dest, int cMax, int staNum) {
        dist[res] = 0;
        int curSta = res;
        while (true) {
            if (curSta == -1)
                break;
            visited[curSta] = true;
            for (int i = 0; i <= staNum; i++) {
                // curSta加入已遍历集合后，更新所有站点的路径
                //// (map[curNode][i] + dist[curNode] < dist[i])会溢出
                if (!visited[i] && map[curSta][i] <= dist[i] - dist[curSta]) {
                    if (edgeTo[i] == null)
                        edgeTo[i] = new ArrayList<Integer>();
                    if (map[curSta][i] + dist[curSta] < dist[i]) {
                        dist[i] = map[curSta][i] + dist[curSta];
                        edgeTo[i].clear();
                        edgeTo[i].add(curSta);
                    } else
                        edgeTo[i].add(curSta);
                }
            }
            int min = Integer.MAX_VALUE, index = -1;
            for (int i = 0; i <= staNum; i++) {
                if (!visited[i] && dist[i] < min) {
                    min = dist[i];
                    index = i;
                }
            }
            curSta = index;
        }
    }
}

class NeedBike {
    int needBike;
    int backBike;
    ArrayList<Integer> road;

    @Override
    public String toString() {
        return "NeedBike [needBike=" + needBike + ", backBike=" + backBike + "]";
    }
}

编辑于 2017-09-24 13:34:01 回复(0)
想买蓝钻头像 想买蓝钻
第一题全部做出来的题目，留个念吧。
思路：
dijkstra求源点0到所有点的最短路径，并把路径记录下来，这个大家应该都懂。
比较坑的是求自行车站送出和收回的自行车。
据观察样例数据，自行车中心送出和收回自行车的过程为从0开始沿路径到目标点，该过程中调整沿路车站，不够马上送自行车过来，有多就拿着到下一站，到目标点后多余的自行车就拿回到中心站。
对应代码过程为：
                        int temp = Sp;
                        vector<int> currentPath;
                        currentPath.clear();
                        while (temp != 0) {
                            currentPath.insert(currentPath.begin(), temp);
                            temp = path[temp];
                        }
                        int surplusBike = 0;
                        int currentSend = 0;
                        for (int i = 0; i < currentPath.size(); i++) {
                            surplusBike += bikeNum[currentPath[i]] - Cmax / 2;
                            if (surplusBike < 0) {
                                currentSend -= surplusBike;
                                surplusBike = 0;
                            }
                        }
                        send = currentSend;
                        take = surplusBike;


全部代码如下：
#include<iostream>
#include<climits>
#include<string>
#include<vector>
using namespace std;
int main() {
    int Cmax = 0;
    int N =0;
    int Sp = 0;
    int edgeNum = 0;
    int bikeNum[501];
    bool reach[501];
    int path[501];
    int distance[501];
    int stationEdge[501][501];
    for (int i = 0; i < 501; i++) {
        bikeNum[i] = 0;
        reach[i] = false;
        path[i] = -1;
        distance[i] = INT_MAX;
        for (int j = 0; j < 501; j++) {
            stationEdge[i][j] = -1;
        }
    }
    cin >> Cmax >> N >> Sp >> edgeNum;
    for (int i = 1; i <= N; i++) {
        cin >> bikeNum[i];
    }
    int edgeStart, edgeEnd,value;
    for (int i = 0; i < edgeNum; i++) {
        cin >> edgeStart >> edgeEnd>>value;
        stationEdge[edgeStart][edgeEnd] = value;
        stationEdge[edgeEnd][edgeStart] = value;
    }
    reach[0] = true;
    distance[0] = 0;
    int next = 0;
    
    int send = 0;
    int take = 0;
    for (int i = 0; i <= N; i++) {
        
        for (int k = 0; k <= N; k++) {
            if (stationEdge[next][k] > 0) {
                if (distance[next] + stationEdge[next][k] < distance[k]) {
                    distance[k] = distance[next] + stationEdge[next][k];
                    path[k] = next;
                    if (k == Sp) {
                        int temp = Sp;
                        vector<int> currentPath;
                        currentPath.clear();
                        while (temp != 0) {
                            currentPath.insert(currentPath.begin(), temp);
                            temp = path[temp];
                        }
                        int surplusBike = 0;
                        int currentSend = 0;
                        for (int i = 0; i < currentPath.size(); i++) {
                            surplusBike += bikeNum[currentPath[i]] - Cmax / 2;
                            if (surplusBike < 0) {
                                currentSend -= surplusBike;
                                surplusBike = 0;
                            }
                        }
                        send = currentSend;
                        take = surplusBike;
                    }
                    
                }
                else if (distance[k] != INT_MAX&&k == Sp&&distance[next] + stationEdge[next][k] == distance[k]) {
                    int temp = next;
                    vector<int> currentPath;
                    currentPath.clear();
                    while (temp != 0) {
                        currentPath.insert(currentPath.begin(), temp);
                        temp = path[temp];
                    }
                    currentPath.push_back(Sp);
                    int surplusBike = 0;
                    int currentSend = 0;
                    for (int i = 0; i < currentPath.size(); i++) {
                        surplusBike += bikeNum[currentPath[i]] - Cmax / 2;
                        if (surplusBike < 0) {
                            currentSend -= surplusBike;
                            surplusBike = 0;
                        }
                    }
                    if (currentSend < send) {
                        send = currentSend;
                        take = surplusBike;
                        path[Sp] = next;
                    }
                    
                }
                
            }
        }
        int shortest = INT_MAX;
        
        for (int j = 1; j <= N; j++) {
            if (reach[j]==false && distance[j]<shortest) {
                shortest = distance[j];
                next = j;
            }
        }
        reach[next] = true;
    }
    int zero = 0;
    string out;
    out += " " + to_string(take);
    int temp = Sp;
    while (temp != 0) {
        out ="->"+ to_string(temp) + out;
        temp = path[temp];
    }
    out = "0" + out;
    out = to_string(send) + " " + out;
    cout << out;
    
}

发表于 2018-02-11 11:47:30 回复(0)
C/C++
萧丿竹影头像 萧丿竹影 
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;
int Cmax,N,Sp,M;  //站台最大自行车数，站台数，问题站台号，道路数
int costTime,outBike,inBike; //花费总时间，
int resultOutBike,resultInBike; //带出带回的自行车数量
int resultTime=INT_MAX;    //最终花费时间
vector<int> bike,path,resultPath;      //各站台自行车数,路径，最短路径
vector<vector<int>> timess;  //各道路所花费的时间
vector<bool> visited;   //站台是否已访问
void dfs(int start,int index,int end);
int main()
{
//提高cin效率
ios::sync_with_stdio(false);
int m,n,dist;
cin>>Cmax>>N>>Sp>>M;
bike.resize(N+1,0);
visited.resize(N+1,false);
timess.resize(N+1,vector<int>(N+1,0));
for(int i=1; i!=N+1; ++i)
{
cin>>bike[i];
}
for(int i=0; i!=M; ++i)
{
cin>>m>>n>>dist;
timess[m][n]=dist;
timess[n][m]=dist;
}
dfs(0,0,Sp);
cout<<resultOutBike<<" 0";
for(int i=1; i!=resultPath.size(); ++i)
{
cout<<"->"<<resultPath[i];
}
cout<<" "<<resultInBike;
return 0;
}
void dfs(int start,int index,int end)
{
//访问节点记录路径和时间
visited[index]=true;
costTime+=timess[start][index];
path.push_back(index);
if(index==end)
{
//计算带出去和带回来的车
inBike=0;
outBike=0;
for(int i=1; i!=path.size(); ++i)
{
if(bike[path[i]]>Cmax/2)
inBike+=bike[path[i]]-Cmax/2;
else if((Cmax/2-bike[path[i]])<inBike)
inBike-=Cmax/2-bike[path[i]];
else
{
outBike+=Cmax/2-bike[path[i]]-inBike;
inBike=0;
}
}
//判断是否为最佳路径
if(costTime<resultTime)
{
resultTime=costTime;
resultOutBike=outBike;
resultInBike=inBike;
resultPath=path;
}
else if(costTime==resultTime)
{
if(outBike<resultOutBike)
{
resultOutBike=outBike;
resultInBike=inBike;
resultPath=path;
}
}
}
//递归
else
{
for(int i=1; i!=N+1; ++i)
{
if(!visited[i]&&timess[index][i]!=0)
dfs(index,i,end);
}
}
//回溯
visited[index]=false;
costTime-=timess[start][index];
path.pop_back();
}

编辑于 2017-03-05 16:56:51 回复(0)
superman2020头像 superman2020 
#include<bits/stdc++.h>
using namespace std;
const int inf=0x7ffffff;
int M[510][510],c,n,m,x,v[510],ansx,ansy,anscost,anssent;
vector<int>ans,temp;
void dfs(int cur,int cost,int sent,int back){
   temp.push_back(cur);
   if(cur==x){
      if(cost<anscost||(cost==anscost&&sent<anssent)){
            anscost=cost;
            anssent=sent;
            ans=temp;
            ansx=sent;
            ansy=back;
      }
      return;
   }
   for(int i=1;i<=n;i++){
      if(M[cur][i]!=-1&&!v[i]){
         v[i]=1;
         if(M[i][i]<c/2){
            if(back+M[i][i]>=c/2) dfs(i,cost+M[cur][i],sent,back-(c/2-M[i][i]));
            else dfs(i,cost+M[cur][i],sent+c/2-back-M[i][i],0);
         }
         else dfs(i,cost+M[cur][i],sent,back+M[i][i]-c/2);
         temp.pop_back();
         v[i]=0;
      }
   }
}
int main()
{
    while(~scanf("%d %d %d %d",&c,&n,&x,&m)){
      for(int i=1;i<=n;i++) scanf("%d",&M[i][i]);
      for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
           if(i!=j) M[i][j]=-1;
        }
      }
      for(int i=0;i<m;i++){
         int x,y,z;scanf("%d %d %d",&x,&y,&z);
         M[x][y]=z;M[y][x]=z;
      }
      ans.clear();
      temp.clear();
      memset(v,0,sizeof(v));
      anscost=inf;anssent=inf;
      dfs(0,0,0,0);
      printf("%d ",ansx);
      for(int i=0;i<ans.size()-1;i++) printf("%d->",ans[i]);
      printf("%d ",ans[ans.size()-1]);
      printf("%d\n",ansy);
    }
}

发表于 2016-08-17 22:43:13 回复(4)
DestinyX头像 DestinyX
使用邻接表来表示图（graph）；
然后使用djistra来求单源最短距离；
再然后用深度搜索来根据p每个节点之前的path值来逆向推出所有的最短路径
之后根据所得的最短路径来获取最佳的结果；
就是路径上每个节点来满足，如果不够要从0节点来补充，够的话就把多余的往下面传
发表于 2015-09-09 17:10:26 回复(0)
LOSZED头像 LOSZED 
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
const int N = 501;
int bike[N], g[N][N];
bool vis[N];
int min_dis = INT_MAX, send_bikes, back_bikes;
vector<int> res, t;
int c, n, s, m;

void dfs(int x, int dis, int bikes, int send) // dis为当前路径距离，bikes为当前自行车变化量，send为当前送出量
{
    if (dis > min_dis) // 剪枝，如果当前路径已大于当前最短路径，则返回
        return;
    if (x == s)
    {
        int back = send - bikes; // 送回自行车的数量
        if (dis < min_dis)
        {
            min_dis = dis;
            send_bikes = send;
            back_bikes = back;
            res = t;
        }
        else if (dis == min_dis)
        {
            if (send < send_bikes)
            {
                send_bikes = send;
                back_bikes = back;
                res = t;
            }
            else if (send == send_bikes)
            {
                if (back < back_bikes)
                {
                    back_bikes = back;
                    res = t;
                }
            }
        }
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i] && g[x][i])
        {
            vis[i] = true;
            t.push_back(i);
            dfs(i, dis + g[x][i], bikes + bike[i], max(send, bikes + bike[i])); // 搜索过程中最大变化量即为要送出自行车的数量
            t.pop_back(); // 回溯
            vis[i] = false;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> c >> n >> s >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> bike[i];
        bike[i] = c / 2 - bike[i]; // 输入时将自行车的数量转为变化量（正数送出，负数送回）
    }
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    dfs(0, 0, 0, 0);
    cout << send_bikes << " " << 0;
    for (auto path : res)
        cout << "->" << path;
    cout << " " << back_bikes << endl;
    return 0;
}

编辑于 2020-06-18 09:20:48 回复(0)
我就来瞄一眼头像 我就来瞄一眼
英语太差了读题真的难！！！ 
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

struct edge { int w, v;};

int cmax, n, sp, m, x, y, z;
int c[501], dis[250010];
typedef pair<int,int> P;
vector<edge> vec[250010];
vector<P> path;

void print(int s, int t) {
	vector<int> tmp;
	int now = t;
	int cnt = 0, send = 0, back = 0;
	while(now != -1) { //逆序回退路径 
		tmp.push_back(now);
		cnt++;
		now = path[now].first;
	}
	for(int i = tmp.size()-2; i >= 0; i--) { //这里很重要！！！ 
		if(c[tmp[i]] + back < cmax/2) {
			send += cmax/2 - back - c[tmp[i]];
			back = 0;
		} else {
			back += c[tmp[i]] - cmax/2;
		}
	}
	cout << send << " ";
	for(int i = tmp.size()-1; i >= 0; i--) {
		if(i != tmp.size()-1) {
			cout << "->";
		}
		cout << tmp[i];		
	}
	cout << " " << back << endl;
}
void djs(int s, int t) {
	for(int i = 0; i <= n; i++) path.push_back(P(-1,c[i]));
	
	memset(dis, INF, sizeof(dis));
	priority_queue<P, vector<P>, greater<P> > que;
	dis[s] = 0;
	que.push(P(0, s));
	
	while(!que.empty()) {
		P p = que.top();
		que.pop();
		int v = p.second;
		if(dis[v] < p.first) continue;
		for(int i = 0; i < vec[v].size(); i++) {
			edge e = vec[v][i];
			if(dis[e.v] > dis[v] + e.w || 
			(dis[e.v] == dis[v] + e.w && path[v].second + c[v] > path[e.v].second)) { //路径相同时选择路径上自行车数目更大的 
				dis[e.v] = dis[v] + e.w;
				path[e.v].first = v;//记录路径 
				path[e.v].second = path[v].second + c[v];//记录路径上总的自行车数目 
				que.push(P(e.w+dis[v], e.v));
			}
		}
	}
	print(s,t);
}
int main() {
	ios::sync_with_stdio(false);
	cin >> cmax >> n >> sp >> m;
	for(int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	for(int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		vec[x].push_back(edge{z,y});
		vec[y].push_back(edge{z,x});
	}
	djs(0,sp);
	return 0;
} 


发表于 2020-01-02 19:40:58 回复(0)
ntwbvdbl_oe头像 ntwbvdbl_oe
翻了一圈没人写dp
数据太水把dfs放过去了
导致大家都以为正解是dfs😑
发表于 2019-11-25 10:26:35 回复(0)
Jexer头像 Jexer
数据太水了。
发表于 2019-10-29 20:34:11 回复(0)
牛客5472335号头像 牛客5472335号

dfs

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

int v[502][502]; //cost表
int num[502],visit[502];  //补充权表和visit表
int c, n, sp, m;
int cost = 0, mincost = 1000000, rent = 0, //每个考虑的权都需两个变量
    maxrent = 0, minrent = 1000000, backnum = 0;
vector<int> res, t; //答案记录表

void dfs(int s) {
    if (s == sp) {
        //最小花费最优先
        if (cost < mincost) {
            mincost = cost;
            minrent = maxrent;//maxrent就是途中记录的最大发车数
            //rent记录途中车的数量变化量,maxrent-rent就是最后的回车量
            backnum = maxrent - rent;
            res = t;
        }
        //当花费一样,先考虑发车数量小者
        else if (cost == mincost && maxrent < minrent) {
            minrent = maxrent;
            backnum = maxrent - rent;
            res = t;
        }
        //当花费一样,发车数一样, 考虑回车数量小者
        else if (cost == mincost && maxrent == minrent 
                && maxrent - rent < backnum) {
            backnum = maxrent - rent;
            res = t;
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (visit[i]==0&&v[s][i] > 0) {
            visit[i] = 1;
            cost += v[s][i];
            rent += (c / 2 - num[i]);
            int temp = maxrent;
            maxrent = max(rent, maxrent);
            t.push_back(i);

            dfs(i);

            //深度优先搜索时,注意回溯
            t.pop_back();
            maxrent = temp;
            rent -= (c / 2 - num[i]);
            cost -= v[s][i];
            visit[i] = 0;
        }
    }
}
int main() {
    scanf("%d %d %d %d", &c, &n, &sp, &m);
    for (int i = 1; i <= n; i++)scanf("%d", &num[i]);
    int st, e, w;
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &st, &e);
        scanf("%d", &v[e][st]);
        v[st][e] = v[e][st];
    }
    fill(visit, visit + 502, 0);
    dfs(0);
    printf("%d 0", minrent);
    for (int i = 0; i < res.size(); i++)printf("->%d", res[i]);
    printf(" %d", backnum);
    system("pause");
    return 0;
}
编辑于 2019-08-04 02:47:54 回复(0)
~~好好工作~~头像 ~~好好工作~~

DFS+回溯。
投放需要按照路径顺序计算。
相同时间开销，先看带过去的车数目，再看带回的车数目。
一个用例一个用例的排雷，用我4个小时了。。。 

import java.util.*;

public class Main {

    public static class Path {
        static int bestPathTime = Integer.MAX_VALUE;
        static Path bestPath;
        int[] path;
        int takeBikeSum;
        int bringBikeSum;
        int time;

        Path(ArrayList<Integer> path1, int[][] graph, int[] station, int cMax) {
            this.path = new int[path1.size()];
            this.path[0] = 0;
            this.takeBikeSum = 0;
            this.bringBikeSum = 0;
            this.time = 0;
            for (int i = 1; i < path1.size(); ++i) {
                this.path[i] = path1.get(i);
                int stationBikes = station[this.path[i] - 1];
                if (stationBikes < cMax / 2) {
                    int need = cMax / 2 - stationBikes;
                    if (need <= this.bringBikeSum)
                        this.bringBikeSum -= need;
                    else {
                        this.takeBikeSum += need - this.bringBikeSum;
                        this.bringBikeSum = 0;
                    }
                }else if (stationBikes > cMax / 2) {
                    this.bringBikeSum += stationBikes - cMax / 2;
                }
                this.time += graph[path1.get(i - 1)][path1.get(i)];
            }
            if (this.time < bestPathTime) {
                Path.bestPath = this;
                bestPathTime = this.time;
            } else if (this.time == bestPathTime) {
                if (bestPath.bringBikeSum > this.bringBikeSum) {
                    Path.bestPath = this;
                    bestPathTime = this.time;
                }
            }
        }

        public String toString() {
            StringBuilder pathStr = new StringBuilder();
            for (int i = 0; i < this.path.length; ++i) {
                pathStr.append(i == this.path.length - 1 ? path[i] : path[i] + "->");
            }
            return this.takeBikeSum + " " + pathStr.toString() + " " + this.bringBikeSum;
        }
    }

    static int cMax;
    static int N;
    static int Sp;
    static int M;

    static int[] station;
    static int[][] graph;

    static ArrayList<Integer> currentPath = new ArrayList<>();
    static int[][] visited;

    public static void dfs(int start, int end) {
        int minIndex = 0;
        int min;
        int currentNode = start;
        HashSet<Integer> nodesCaled = new HashSet<>();
        nodesCaled.add(start);
        while (true) {
            min = Integer.MAX_VALUE / 2;
            boolean findNode = false;
            // 1.选取最小节点
            for (int i = 0; i < N + 1; ++i) {
                if (nodesCaled.contains(i))
                    continue;
                int val = graph[currentNode][i];
                if (visited[currentNode][i] != -1 && val != -1 && min > val) {
                    min = val;
                    minIndex = i;
                    findNode = true;
                }
            }
            if (findNode) {
                visited[currentNode][minIndex] = -1;
                currentNode = minIndex;
                currentPath.add(minIndex);
                nodesCaled.add(minIndex);
                // 2.判断到达
                if (minIndex == Sp) {
                    new Path(currentPath, graph, station, cMax);
                } else {// 未到达，继续寻找
                    continue;
                }
            }
            // 3.开始回溯（未找到路径，回溯；已经到达，开始找其它路径，回溯）
            nodesCaled.remove(currentPath.get(currentPath.size() - 1));
            for (int j = 0; j < N + 1; ++j) {
                visited[currentPath.get(currentPath.size() - 1)][j] = 
                        currentPath.get(currentPath.size() - 1) == j ? -1 : 1;
//                visited[j][currentPath.get(currentPath.size() - 1)] =visited[currentPath.get(currentPath.size() - 1)][j]; 

            }
            currentPath.remove(currentPath.size() - 1);
            if (!currentPath.isEmpty())
                currentNode = currentPath.get(currentPath.size() - 1);
            else
                break;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        cMax = sc.nextInt();
        N = sc.nextInt();
        Sp = sc.nextInt();
        M = sc.nextInt();
        station = new int[N];
        for (int i = 0; i < N; ++i) {
            station[i] = sc.nextInt();
        }

        graph = new int[1 + N][1 + N];
        visited = new int[1 + N][1 + N];
        for (int i = 0; i < 1 + N; ++i) {
            for (int j = 0; j < 1 + N; ++j) {
                graph[i][j] = i == j ? 0 : -1;
                visited[i][j] = i == j ? -1 : 1;
            }
        }
        int start, end, time;
        for (int i = 0; i < M; ++i) {
            start = sc.nextInt();
            end = sc.nextInt();
            time = sc.nextInt();
            graph[start][end] = time;
            graph[end][start] = time;
        }
        sc.close();
        currentPath.add(0);
        dfs(0, Sp);
        System.out.println(Path.bestPath);
    }
}
发表于 2019-07-29 13:48:11 回复(1)
Myhui头像 Myhui 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=510;
const int INF=1000000000;
vector<int> pre[maxn],path,temppath;                 //前驱数组，最短路径，临时路径
int G[maxn][maxn],d[maxn],weight[maxn];
bool vis[maxn]={false};
int cmax,n,final,edge,minNeed=INF,minRemain=INF;     //minNeed为最少携带数量，minRemain为最少带回数量
void Dijkstra(int s){
    fill(d,d+maxn,INF);d[s]=0;                       //初始化，s为起点，s到自己本身最短路径为0
    for(int i=0;i<=n;i++){                           //本题起点外有n个点，故循环n+1次
        int u=-1,min=INF;
        for(int j=0;j<=n;j++){                       //找到未访问的结点中d[]最小的
            if(vis[j]==false&&d[j]<min){
                u=j;min=d[j];
            }
        }
        if(u==-1) break;                             //找不到小于INF的d[u]，说明剩下的结点和s不连通                          
        vis[u]=true;
        for(int v=0;v<=n;v++){
            if(vis[v]==false&&G[u][v]!=INF){         //若v未访问且u与v有边相连
                if(d[u]+G[u][v]<d[v]){
                    d[v]=d[u]+G[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if(d[u]+G[u][v]==d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}
void DFS(int v){                                    //从后往前用pre前驱遍历
    temppath.push_back(v);                          //先将本结点加入到临时路径中
    if(v==0){                                       //递归边界（到了起点）
        int need=0,remain=0;
        for(int i=temppath.size()-1;i>=0;i--){      //对temppath倒着枚举（结点是DFS倒着入temppath的，相当于顺序枚举）
            int now=temppath[i];
            if(weight[now]>0)                       //点权大于0，要带走多出来的一部分
                remain+=weight[now];
            else{                                   //点权不大于0，需要补给
                if(remain>abs(weight[now]))         //当前持有量足够补给
                    remain-=abs(weight[now]);
                else{                               //当前持有量不够补给
                    need+=(abs(weight[now])-remain);//记下不够的部分有多少
                    remain=0;
                }
            }
        }
        if(need<minNeed){                           //从本条路径需要从起点携带的量更少
            minNeed=need;minRemain=remain;path=temppath;
        }
        else if(need==minNeed&&remain<minRemain){   //携带量相同，带回（多余）的数量更少
            minRemain=remain;path=temppath;
        }
        temppath.pop_back();                      
        return;
    }
    for(int i=0;i<pre[v].size();i++)                 //递归访问v的其他前驱，到其他最短路径
        DFS(pre[v][i]);
        temppath.pop_back();                             //将刚加入的结点删除（回溯）
    }
int main(){
    cin>>cmax>>n>>final>>edge;
    fill(G[0],G[0]+maxn*maxn,INF);                   //初始化图
    for(int i=1;i<=n;i++){
        cin>>weight[i];
        weight[i]=weight[i]-cmax/2;                  //点权减去题意给定值
    }
    for(int i=0;i<edge;i++){
        int id1,id2;
        cin>>id1>>id2;
        cin>>G[id1][id2];
        G[id2][id1]=G[id1][id2];
    }
    Dijkstra(0);
    DFS(final);                                      //从终点往回遍历
    cout<<minNeed<<" 0";
    for(int i=path.size()-2;i>=0;i--)
        cout<<"->"<<path[i];
        cout<<" "<<minRemain;
    return 0;
}

编辑于 2019-02-08 12:50:21 回复(0)
MniQ头像 MniQ
#include <iostream>
#include <vector>
using namespace std;

//1003 Emergency
//站点下标从1开始,PBMC下标固定为0
//小迪找出最短路，可能有复数多条
//对每条最短路dfs求需要送回PBMC的数量，取最小的一条
//本题的坑在于站点下标[1,n]，不是平时的[0,n)，经常会弄错


#define inf 1e9
#define maxn 501


//全局变量存最优解
int min_need = inf, min_take = inf;
vector<int> bestpath;


void dfs(int pos, vector<int> path, vector<int> *pre, int *resource) {
    //反向追溯，多条最短路都可以到达0点时
    //每次抵达0点计算一下need和take，取最优解
    if (pos == 0) {
        //回到0点，此时path内存着一条从Sp到{0的下一个点}的路径
        //所以应该逆序访问，这样才是{0的下一个点}~`Sp
        int need = 0, carrier = 0;
        for (int i = path.size() - 1; i >= 0; --i) {
            if (resource[path[i]] < 0) {
                //调整need与carrier
                if (carrier + resource[path[i]] >= 0) {
                    //身上携带的可以满足当前结点的需求
                    //need不变
                    carrier += resource[path[i]];
                }
                else {
                    //carrier不能满足当前结点的需求
                    need -= (carrier + resource[path[i]]);
                    carrier = 0;
                }
            }
            else {
                //该点拥有资源>=0
                carrier += resource[path[i]];
                //之所以>0时，不需要调整need与carrier
                //是因为多余的车只能向后面运输，不能满足前面空虚的need
            }
        }//end-for

        //到此本最短路已计算完毕，开始比较
        if (need < min_need) {
            min_need = need;
            min_take = carrier;//需要归还PBMC的数量
            bestpath = path;
        }
        else if (need == min_need && carrier < min_take) {
            min_take = carrier;
            bestpath = path;
        }

        return; //可以不必运行下面的语句了
    }

    //dfs的精髓！！！！！！！！
    path.push_back(pos);
    for (int i = 0; i < pre[pos].size(); ++i) {
        dfs(pre[pos][i], path, pre, resource);
    }
    path.pop_back();
}

int main() {
    int c, n, sp, m; //c<=100,n<=500


    int g[maxn][maxn] = {};
    int dist[maxn] = {}, visited[maxn] = {};
    vector<int> pre[maxn];
    int resource[maxn] = {};
    int need[maxn] = {};
    int carrier = 0, demand = 0, sentback = 0;


    cin >> c >> n >> sp >> m;

    //输入每个站点当前信息
    for (int i = 1; i <= n; i++) {
        //本题特殊，范围[1,n]
        int ci;
        cin >> ci;
        //以perfect状态为基点，正数表示富余，负数表示缺少
        resource[i] = ci - c / 2;
    }

    //初始化图
    fill(g[0], g[0] + 500 * 500, inf);

    //输入图
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = z;
        g[y][x] = z;
    }

    //初始化dist[] , visited[] , cnt[], gather[]
    for (int i = 0; i <= n; i++) {
        //本题特殊,PBMC为0，外面还有1~n编号的结点，所以范围是[0,n]
        //不写这个<=的等于号,则本循环内更新不了dist[n]
        //则dist[n]=0，经过后面的小迪也依然还是0，就出错了
        dist[i] = g[0][i];
    }
    dist[0] = 0;  //不这样写的话，本题默认的g[0][0]=inf，第一次循环取不到0点，就不能从0开始更新cnt[]与gather[]



    //小迪
    int k, min;
    for (int i = 0; i < n; i++) {
        min = inf;
        for (int j = 0; j < n; j++) {
            if (!visited[j]) {
                if (dist[j] < min) {
                    min = dist[j];
                    k = j;
                }
            }
        }
        //已找到最小k
        visited[k] = 1;
        //更新dist
        for (int w = 1; w <= n; w++) {
            //本题特殊，要更新的邻接点范围是[1,n]
            if (!visited[w] && g[k][w] < inf) { //未访问过的k的邻接点w
                if (dist[k] + g[k][w] < dist[w]) {
                    //更新最短路
                    dist[w] = dist[k] + g[k][w];
                    //覆盖前置结点
                    pre[w].clear();
                    pre[w].push_back(k);
                }
                else if (dist[k] + g[k][w] == dist[w]) {
                    //路径长度相同时，最短路直接叠加
                    pre[w].push_back(k);
                }
            }//-end if
        }//end-for

    }
    //end-dijkstra


    //从问题结点sp开始统计需要运回的与带来的
    vector<int> path;
    dfs(sp, path, pre, resource);

    //输出
    cout << min_need << " " << 0;
    for (int i = bestpath.size() - 1; i >= 0; --i) {
        cout << "->" << bestpath[i];
    }
    cout << " " << min_take;


    return 0;
}
发表于 2019-01-21 23:37:09 回复(0)
C/C++
RicardoZi头像 RicardoZi 
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 500 +2;
const int INF = 0x3f3f3f3f;

struct Dijkstra{
    struct Edge{
        int to, dist;
        Edge(){}
        Edge(int v, int c):to(v), dist(c) {}
    };
    vector<Edge> G[maxn];
    vector<int> road;
    int d[maxn], done[maxn];
    int pre[maxn], take[maxn];
    int bikes[maxn]={0};
    int c_perfect, node_num, edge_num;
    int bring = 0;

    void AddEdge(){
        int s1, s2, l;
        scanf("%d %d %d", &s1, &s2, &l);
        Edge e(s2, l);
        G[s1].push_back(e);
        e.to = s1;
        G[s2].push_back(e);
    }

    void init(int c_max, int n, int m){
        c_perfect = c_max / 2;
        node_num = n; 
        edge_num = m;
        for(int i=1; i<=n; i++)
            scanf("%d", &bikes[i]);
        for(int i=0; i<m; i++) AddEdge();
    }

    void dijkstra(int s){
        priority_queue<pii, vector<pii>, greater<pii> >Q;
        memset(d, INF, sizeof(d));
        memset(done, 0, sizeof(done));
        memset(take, INF, sizeof(take));
        memset(pre, -1, sizeof(pre));
        d[s] = 0;
        take[s] = 0;
        Q.push(make_pair(d[s], s));
        while(!Q.empty()){
            pii p = Q.top();
            Q.pop();
            int u = p.second;
            if(done[u]) continue;
            done[u] = 1;
            for(unsigned int i=0; i<G[u].size(); i++){
                Edge e = G[u][i];
                int v = e.to;
                if(done[v]) continue;
                if(d[v] > d[u] + e.dist || (d[v] == d[u] + e.dist && take[v] <  take[u] + bikes[v])){
                    d[v] = d[u] + e.dist;
                    take[v] = take[u] + bikes[v];
                    pre[v] = u;
                    Q.push(make_pair(d[v], v));
                }
            }
        }
    }

    void cal_road(int s){
        if(s == 0) return;
        else{
            cal_road(pre[s]);
            road.push_back(s);
        }
    }

    void cal_in_out(){
        int len = road.size();
        road.push_back(0);
        for(int i=0; i<len; i++){
            int now_pos = road[i];
            int next_pos = road[i+1];
            int need = bikes[now_pos] - c_perfect;
            if(need >= 0) bikes[next_pos] += need;
            else bring -= need;
        }
    }
    
    void show_result(){
        printf("%d 0", bring);
        for(int i=0; i<road.size()-1; i++){
            printf("->%d", road[i]);
        }
        printf(" %d\n", bikes[0]);
    }
};  

int main(){
    int c_max, n, Sp, m;
    Dijkstra g;
    scanf("%d %d %d %d", &c_max, &n, &Sp, &m);
    g.init(c_max, n, m);
    g.dijkstra(0);
    g.cal_road(Sp);
    g.cal_in_out();
    g.show_result();
    return 0;
}

编辑于 2017-09-09 14:33:15 回复(0)
小ks强头像 小ks强 
测试用例:
100 6 1 15
78 54 0 37 36 82
0 1 7
0 2 4
0 3 7
0 4 7
0 5 2
1 2 9
1 3 1
1 4 2
1 5 5
2 3 1
2 4 2
2 5 7
3 4 4
3 5 7
4 5 7

对应输出应该为:
46 0->2->3->1 28

你的输出为:

18 0->2->3->1 0
这个例子是错的呀，你们都过了么

发表于 2017-05-11 17:19:26 回复(2)
老石基头像 老石基 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
	private static int mintime = Integer.MAX_VALUE;
	private static List<Integer> path = new ArrayList<Integer>();
	private static List<Integer> result;
	private static int[] C;
	private static int send;
	private static int collect;
	private static int cmax;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		cmax = in.nextInt();//最大容量Cmax (<= 100)
		int n = in.nextInt();//站的总数N (<= 500), the total number of stations
		//第二行包含N个非负数Ç
		int sp = in.nextInt();//目的地Sp, the index of the problem station 
		int m = in.nextInt();//道路的数量 M, the number of roads.
		C = new int[n+1];
		int[][] M = new int[n+1][n+1];
		boolean[] visited = new boolean[n+1];
		for(int i = 1;i<=n;i++)
			C[i] = in.nextInt();
		for(int i = 0;i<m;i++){
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();
			M[start][end] = time;
			M[end][start] = time;
		}
		dfn(M, visited, 0, 0, 0, sp);
		System.out.print(send+" ");
		for(int i = 0;i<result.size()-1;i++)
			System.out.print(result.get(i)+"->");
		System.out.print(result.get(result.size()-1)+" ");
		System.out.println(collect);
	}
	public static void dfn(int[][] M,boolean[] visited,int from,int cur,int time,int sp){
	    path.add(cur);
	    visited[cur] = true;
	    time += M[from][cur];
		if(cur==sp){
			int s = 0, c = 0;
			for(int i = 1;i<path.size();i++){
				int index = path.get(i);
				if(C[index] > cmax/2) {
	                c += C[index] -cmax/2;
	            } else {
	                if((cmax/2 - C[index]) < c) {
	                    c -= (cmax/2 - C[index]);
	                } else {
	                    s += (cmax/2 - C[index]) - c;
	                    c = 0;
	                }
	            }
			}
			if (time < mintime) {
				mintime = time;
				result = new ArrayList<Integer>(path);
				send = s;
				collect = c;
			}else if(time==mintime){
				if (s < send) {
					result = new ArrayList<Integer>(path);
					send = s;
					collect = c;
				} else if (s == send && c <collect) {
					result = new ArrayList<Integer>(path);
					send = s;
					collect = c;
				}
			}
		}else{
	        for(int i=1; i<M[cur].length; i++) {
	            if(M[cur][i] != 0&& !visited[i])
	                dfn(M, visited, cur, i, time, sp);
	        }
		}
	    path.remove(path.size()-1);
	    visited[cur] = false;
	}
}

编辑于 2016-06-19 19:57:20 回复(0)
啥头像 啥
总体思路：
      深搜可以求出两点间的所有可达路径
      只要在找到可行路径时判断当前路径是否是更优路径即可。注意回溯

代码如下： 
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

void dfs(int start, int index, int end);

int cmax, N, sp, M;
int costTimes, outBikes, inBikes;
int resultTimes = INT_MAX;
int resultOutBikes, resultInBikes;
vector<int> bikes, path, resultPath;
vector<vector<int> > times;
vector<bool> visited;

int main()
{
	ios::sync_with_stdio(false);
	// 输入数据
	cin >> cmax >> N >> sp >> M;
	bikes.resize(N+1, 0);
	visited.resize(N+1, false);
	times.resize(N+1, vector<int>(N+1, 0));
	for(int i=1; i<=N; i++) {
		cin >> bikes[i];
	}
	int m, n, dist;
	for(int i=0; i<M; i++) {
		cin >> m >> n >> dist;
		times[m][n] = dist;
		times[n][m] = dist;
	}

	// 深搜并输出结果
	dfs(0, 0, sp);
	cout << resultOutBikes << " 0";
	for(int i=1; i<resultPath.size(); i++) {
		cout << "->" << resultPath[i];
	}
	cout << " " << resultInBikes;

    return 0;
}

void dfs(int start, int index, int end)
{
	// 访问
	visited[index] = true;
	path.push_back(index);
	costTimes += times[start][index];

	// 处理
	if(index == end) {
        // 计算这条路上带去的车和带回的车
        inBikes = 0, outBikes = 0;
	    for(int i=1; i<path.size(); i++) {
            if(bikes[path[i]] > cmax/2) {
                inBikes += bikes[path[i]] -cmax/2;
            } else {
                if((cmax/2 - bikes[path[i]]) < inBikes) {
                    inBikes -= (cmax/2 - bikes[path[i]]);
                } else {
                    outBikes += (cmax/2 - bikes[path[i]]) - inBikes;
                    inBikes = 0;
                }
            }
	    }
        // 判断这条路是否更好
		if(costTimes != resultTimes) {
			if(costTimes < resultTimes) {
				resultTimes = costTimes;
				resultPath = path;
				resultOutBikes = outBikes;
				resultInBikes = inBikes;
			}
		} else if(outBikes != resultOutBikes) {
			if(outBikes < resultOutBikes) {
				resultPath = path;
				resultOutBikes = outBikes;
				resultInBikes = inBikes;
			}
		} else if(inBikes < resultInBikes) {
			resultPath = path;
			resultOutBikes = outBikes;
			resultInBikes = inBikes;
		}
	} else {
	    // 递归
		for(int i=1; i<=N; i++) {
			if(times[index][i] != 0 && !visited[i]) {
				dfs(index, i, end);
			}
		}
	}

	// 回溯
	visited[index] = false;
	path.pop_back();
	costTimes -= times[start][index];
}


编辑于 2015-10-30 17:52:20 回复(4)
提交观点

问题信息

图
难度：
60条回答 24310浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号