1018. Public Bike Management (30)

2019-11-14 09:36:16

字体：大中小

来源：转载

供稿：网友

有个坑：不能把后面多出来的自行车补到前面缺的地方，可用DFS或DIJ DFS方法

#include<iostream>#include<vector>#define INF 0x3f3f3f#define MAX_bike 102#define MAX_V 502using namespace std;int C, N, sp, M;int t_min=INF;int send=0, back=0;vector<int> path;//输出变量int temp_send=0, temp_back=0,temp_min=0;vector<int> temp_path;//临时变量int arc[MAX_V][MAX_V] = {0};//邻接矩阵int bike[MAX_V];//顶点自行车数量bool visited[MAX_V];//bfs中是否被访问void intipath()//对路径求temp_back和temp_send { int temp; temp = 0, temp_send = 0; for (auto x : temp_path) { if (bike[x] + temp < 0) { temp_send += -(bike[x] + temp);temp = 0; } else temp = bike[x] + temp; } temp_back = temp; }void bfs(int index)//bfs{ if (temp_min > t_min) { return; }//剪枝 if (index == sp) { intipath(); if (temp_min < t_min || (temp_min==t_min && temp_send<send)||(temp_min==t_min && temp_send==send && temp_back<back) ) { t_min = temp_min;send = temp_send;back = temp_back;path = temp_path; } return; } for (int t = 1;t <= N;t++) { if (visited[t] == false && arc[index][t] != 0) { visited[t] = true; temp_path.push_back(t); temp_min += arc[index][t]; bfs(t); visited[t] = false;//回溯 temp_path.pop_back(); temp_min -= arc[index][t]; } }}int main(){ cin >> C >> N >> sp >> M; bike[0] = 0; for (int t = 1;t <= N;t++) { cin >> bike[t]; bike[t] -= C / 2; } for (int t = 0;t < M;t++) { int i, j,k; cin >> i >> j >> k; arc[i][j] = arc[j][i]=k; } visited[0] = true; bfs(0); cout << send << " 0"; for (auto it = path.begin();it != path.end();it++) cout << "->" << *it; cout << " " << back << endl; return 0;}

DIJ方法：

#include<iostream>#include<vector>#define MAX_V 502#define MAX_bike 102#define INF 0x3f3f3f//vector保存的路径不包括0using namespace std;vector<vector<int>> temp_path[MAX_V];//临时路径，求所有最短路径解int arc[MAX_V][MAX_V] = {0};//邻接矩阵int bike[MAX_V];//顶点自行车数量int D[MAX_V] = {0};//最短路径int temp_D[MAX_V];//DIJ临时变量int C, N, sp, M;int temp_send, temp_back;vector<int> path;int send=INF, back;//最后要输出的void DIJ(){ for (int t = 1;t <= N;t++) if (arc[0][t] != 0) temp_D[t] = arc[0][t]; while (D[sp] == 0) { int temp_min=INF, temp_v; for (int t = 1;t <= N;t++) if (D[t]==0 && temp_D[t] < temp_min) { temp_min = temp_D[t]; temp_v = t; } D[temp_v] = temp_min; for (auto &x : temp_path[temp_v]) x.push_back(temp_v); for (int t = 1;t <= N;t++)//更新temp_D { if (D[t] == 0 && arc[temp_v][t]!=0) { if (temp_min + arc[temp_v][t] < temp_D[t]) { temp_D[t] = temp_min + arc[temp_v][t]; temp_path[t] = temp_path[temp_v]; } else if (temp_min + arc[temp_v][t] == temp_D[t]) { temp_path[t].insert(temp_path[t].end(), temp_path[temp_v].begin(), temp_path[temp_v].end()); } } } }}void intipath(vector<int> p){ temp_send = 0; int temp = 0; for (auto x : p) { if (temp + bike[x] < 0) { temp_send += -(temp + bike[x]); temp = 0; } else temp = temp + bike[x]; } temp_back = temp;}int main(){ cin >> C >> N >> sp >> M; vector<int> vec; for (int t = 1;t <= N;t++) { cin >> bike[t]; bike[t] -= C / 2; temp_D[t] = INF;//初始化 temp_path[t].push_back(vec); } for (int t = 0;t < M;t++) { int i, j,k; cin >> i >> j >> k; arc[i][j] = arc[j][i] = k; } DIJ(); for (auto x : temp_path[sp]) { intipath(x); if (temp_send < send || (temp_send == send && temp_back < back)) { path = x; send = temp_send; back = temp_back; } } cout << send << " 0"; for (auto x : path) cout << "->" << x; cout << " " << back << endl;}

上一篇：Leetcode 129. Sum Root to Leaf Numbers

下一篇：ChucK初步（6）