[PAT解题报告] Public Bike Management
给定一个无向图，一个点表示有无穷多自行车的车管所，每个点有一定的车，每个点的容量都相同，如果有的点车辆少于容量的一半的话，旧需要从车管所运送自行车过去，顺便把经过点多余的车运回去。给定缺车的节点，需要考虑几个指标：
（1）最短路
（2）需要的运过去车最少
（3）需要运回来的车最少
分析 ：
图的节点不多，可以直接用临接矩阵。求最短路可以同时记录路径，关键是最短路有多条，每条都得记录，我用的vector数组表示每个点的前一个节点的可能性——求出最短路在枚举所有最短路，这个就dfs了，好在数据不大，暴力枚举能过。我求最短路是正着求的，其实可以只求到目的地就行。然后枚举的时候枚举全部路径，这样不太好减枝，因为带入的车数mayin可能会变小……别忘记最后路径要反向，因为是不断往起点找的。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 1000000000;
const int N = 502;
int n;
bool mark[N];
int a[N][N];
int b[N];
int cost[N];
vector<int> pre[N];
vector<int> answer;
int bestin, bestout, m;
void dijkstra() {
for (int i = 0; i < n; ++i) {
cost[i] = inf;
mark[i] = false;
}
cost[0] = 0;
for (int j = 0; j < n; ++j) {
int k = -1;
for (int i = 0; i < n; ++i) {
if ((!mark[i]) && ((k < 0) || (cost[i] < cost[k]))) {
k = i;
}
}
mark[k] = true;
for (int i = 0; i < n; ++i) {
if ((!mark[i]) && (a[k][i] < inf)) {
int temp = cost[k] + a[k][i];
if (temp < cost[i]) {
pre[i].resize(1);
pre[i][0] = k;
cost[i] = temp;
}
else if (temp == cost[i]) {
pre[i].push_back(k);
}
}
}
}
}
void dfs(int now, int mayin, int mayout, vector<int> &path) {
path.push_back(now);
if (now == 0) {
if ((mayin < bestin) || ((mayin == bestin) && (mayout < bestout))) {
bestin = mayin;
bestout = mayout;
answer = path;
}
path.pop_back();
return;
}
if (b[now] >= m) {
mayin -= (b[now] - m);
if (mayin < 0) {
mayout -= mayin;
mayin = 0;
}
}
else {
mayin += m - b[now];
}
for (int i = 0; i < pre[now].size(); ++i) {
dfs(pre[now][i], mayin, mayout, path);
}
path.pop_back();
}
int main() {
int p, to;
scanf("%d%d%d%d",&m,&n,&to,&p);
for (int i = 1; i <= n; ++i) {
scanf("%d",b + i);
}
++n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = inf;
}
}
for (;p;--p) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x][y] = a[y][x] = min(a[x][y],z);
}
m >>= 1;
dijkstra();
bestin = bestout = inf;
vector<int> path;
dfs(to, 0, 0, path);
reverse(answer.begin(), answer.end());
printf("%d ",bestin);
for (int i = 0; i < answer.size(); ++i) {
if (i) {
printf("->");
}
printf("%d", answer[i]);
}
printf(" %d\n",bestout);
return 0;
}
另外一种方法也差不多，就是计算最短路的时候从终点往起点做。这样dfs的时候路径是正向的，还有一个好处是，这样带入车辆的数mayin是不断增加的，所以比较方便剪枝。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 1000000000;
const int N = 502;
int n;
bool mark[N];
int a[N][N];
int b[N];
int cost[N];
vector<int> Next[N];
vector<int> answer;
int to, bestin, bestout, m;
void dijkstra() {
for (int i = 0; i < n; ++i) {
cost[i] = inf;
mark[i] = false;
}
cost[to] = 0;
for (int j = 0; j < n; ++j) {
int k = -1;
for (int i = 0; i < n; ++i) {
if ((!mark[i]) && ((k < 0) || (cost[i] < cost[k]))) {
k = i;
}
}
mark[k] = true;
for (int i = 0; i < n; ++i) {
if ((!mark[i]) && (a[k][i] < inf)) {
int temp = cost[k] + a[k][i];
if (temp < cost[i]) {
Next[i].resize(1);
Next[i][0] = k;
cost[i] = temp;
}
else if (temp == cost[i]) {
Next[i].push_back(k);
}
}
}
}
}
void dfs(int now, int mayin, int mayout, vector<int> &path) {
if (mayin > bestin) {
return;
}
path.push_back(now);
if (b[now] >= m) {
mayout += b[now] - m;
}
else {
mayout -= m - b[now];
if (mayout < 0) {
mayin -= mayout;
mayout = 0;
}
}
if (now == to) {
if ((mayin < bestin) || ((mayin == bestin) && (mayout < bestout))) {
bestin = mayin;
bestout = mayout;
answer = path;
}
path.pop_back();
return;
}
for (int i = 0; i < Next[now].size(); ++i) {
dfs(Next[now][i], mayin, mayout, path);
}
path.pop_back();
}
int main() {
int p;
scanf("%d%d%d%d",&m,&n,&to,&p);
for (int i = 1; i <= n; ++i) {
scanf("%d",b + i);
}
++n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = inf;
}
}
for (;p;--p) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x][y] = a[y][x] = min(a[x][y],z);
}
b[0] = (m >>= 1);
dijkstra();
bestin = bestout = inf;
vector<int> path;
dfs(0, 0, 0, path);
printf("%d ",bestin);
for (int i = 0; i < answer.size(); ++i) {
if (i) {
printf("->");
}
printf("%d", answer[i]);
}
printf(" %d\n",bestout);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1018
