图论的几个重要细节和思路
- 分析原图建新图
- 是否可以转化为DAG来dp解决
- 用板子时端点从0开始而不是1
- 加边的时候注意重边的处理
- 注意输入一条边时，起点终点应该不一样（u != v）
- 无向图的边具有双向性，如果涉及具体枚举某条边的时候，要注意u->v 和 v->u都枚举一遍
Airport Express
原题大意
有两种车票，商务车票和经济车票。由于经济原因，商务车票只能买一张，经济车票可以买多张。车票都是双向的。现在问从起点到终点，的最短路径，以及商务车票在哪个站点用最划算和最后花费的总时间。
算法分析
对于每个给出的起点终点a，b；分别求出到a和到b的单源最短路f(x), g(X)，然后枚举商业线的边T，答案就是f(a) + T(a,b) + g(b)，如果不做商业线就是f(b)或者g(a)；
维护最大值即可。注意每条边要枚举两次。
程序代码
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
const int maxn = 500 + 50;
const int INF = 10000000;
int n, m, k, s, e, x, y, z;
struct Edge{
int from, to, dist;
Edge(int _f, int _to, int _d){
from = _f;
to = _to;
dist = _d;
}
};
vector<int> G[maxn];
vector<Edge> edges;
bool inq[maxn];
int d[maxn], d1[maxn], d2[maxn], p[maxn];
void spfa(int s){
queue<int> Q;
mem(inq, false);
mem(p,-1);
for(int i = 0; i < n; i++) d[i] = INF;
d[s] = 0;
inq[s] = true;
Q.push(s);
while(!Q.empty()){
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = 0; i < G[u].size(); i++){
Edge &e = edges[G[u][i]];
if(d[u] < INF && d[e.to] > d[u] + e.dist){
d[e.to] = d[u] + e.dist;
p[e.to] = u;
if(!inq[e.to]) {
inq[e.to] = true;
Q.push(e.to);
}
}
}
}
}
void AddEdge(Edge e){
edges.pb(e);
int num = edges.size();
G[e.from].pb(num - 1);
}
vector<int> path1[maxn], path2[maxn];
void init(){
for(int i = 0; i < maxn; i++)
G[i].clear(), path1[i].clear(), path2[i].clear();
edges.clear();
}
void getpath(int s, int *dist, vector<int>* path){
spfa(s);
for(int i = 0; i < n; i++){
dist[i] = d[i];
int t = i;
path[i].pb(t);
while(p[t] != -1){
path[i].pb(p[t]);
t = p[t];
}
reverse(path[i].begin(), path[i].end());
}
}
int main(){
// freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int kase = 0;
while(cin >> n >> s >> e){
init();
kase++;
s--,e--;
cin >> m;
for(int i = 0; i < m; i++){
cin >> x >> y >> z;
x--,y--;
AddEdge(Edge(x,y,z));
AddEdge(Edge(y,x,z));
}
vector<int> path;
int ans = -1;
getpath(s, d1, path1);
getpath(e, d2, path2);
ans = d1[e];
//cout << ans << endl;
path = path1[e];
int midpoint = -1;
cin >> k;
for(int i = 0; i < k; i++){
cin >> x >> y >> z;
x--,y--;
int t = 2;
while(t--){
if(d1[x] + d2[y] + z < ans){
ans = d1[x] + d2[y] + z;
midpoint = x;
path.clear();
path = path1[x];
for(int j = path2[y].size()-1; j>=0; j--){
path.pb(path2[y][j]);
}
}
swap(x,y);
}
}
if(kase != 1) cout << "\n";
int i;
for(i = 0; i < path.size()-1; i++)
cout << path[i]+1 << " ";
cout << path[i]+1 << "\n";
if(midpoint != -1) cout << midpoint+1 << "\n";
else cout << "Ticket Not Used\n";
cout << ans << endl;
}
return 0;
}
Walk Through the Forest
原题大意
Jimmy下班后决定每天沿着一条不同的路径回家，欣赏不同的风景。他打算只沿着满足如下条件的（A,B）道路走：存在一条从B出发回家的路，比所有从A出发回家的路径都短。你的任务是计算一共有多少条不同的回家路径。其中公司的编号为1，家的编号为2.
算法分析
求出每个点距离终点的最短路长度d[u]，题中的条件为d[A] > d[B]，所以建新图：当d[A] > d[B]，将有向边A->B加入进去，问起点到终点的走法有几种，转化为DAG，动态规划求解。
程序代码
#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
using namespace std;
const int maxn = 1000 + 50;
const int INF = 1000000000;
int n, m;
struct Edge{
int from, to, dist;
Edge(int _from, int _to, int _dist){
from = _from;
to = _to;
dist = _dist;
}
};
struct Spfa{
vector<Edge> edges;
vector<int> G[maxn];
int d[maxn];
bool inq[maxn];
void Init(){
edges.clear();
for(int i = 0; i < maxn; i++)G[i].clear();
mem(inq, false);
}
void AddEdge(Edge e){
edges.pb(e);
int m = edges.size();
G[e.from].pb(m-1);
}
void spfa(int s){
queue<int> Q;
for(int i = 0; i < n; i++) d[i] = INF;
d[s] = 0;
inq[s] = true;
Q.push(s);
while(!Q.empty()){
int u = Q.front();Q.pop();
inq[u] = false;
for(int i = 0; i < G[u].size(); i++){
Edge &e = edges[G[u][i]];
if(d[u] < INF && d[u] + e.dist < d[e.to]){
d[e.to] = d[u] + e.dist;
if(!inq[e.to]){
inq[e.to] = true;
Q.push(e.to);
}
}
}
}
}
};
Spfa solver;
int dp[maxn];
vector<int> g[maxn];
int dfs(int u){
if(dp[u] != -1) return dp[u];
dp[u] = 1;
int ans = 0;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
ans+=dfs(v);
}
dp[u] *= ans;
return dp[u];
}
int main(){
// freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
while(cin >> n >> m && n){
solver.Init();
mem(dp,-1);
for(int i = 0; i < maxn; i++) g[i].clear();
int u, v, w;
for(int i = 0; i < m; i++){
cin >> u >> v >> w;
u--;
v--;
solver.AddEdge(Edge(u,v,w));
solver.AddEdge(Edge(v,u,w));
}
solver.spfa(1);
for(int i = 0; i < n; i++){
int sz = solver.G[i].size();
for(int j = 0; j < sz; j++){
Edge e = solver.edges[solver.G[i][j]];
if(solver.d[i] > solver.d[e.to]){
g[i].pb(e.to);
}
}
}
dp[1] = 1;
cout << dfs(0) << endl;
}
return 0;
}
Warfare And Logistics
原题大意
1.先求任意两点间的最短路径累加和，其中不连通的边权为L
2.删除任意一条边,求全局最短路径和的最大值。
算法分析
暴力想法就是n次最短路，然后枚举m条边，但是会超时，每次求以src为源点的最短路时，要删除的边一定在src的最短路树上，因为其他的边不会改变结果，这样只要枚举（n-1）条边就可以了，如果有重边删掉之后，要用第二短的边来替代
程序代码
#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 100 + 5;
const int INF = 1000000000;
int n, m;
ll L;
struct Edge{
int from, to;
ll dist;
Edge(int _from, int _to, ll _dist){
from = _from;
to = _to;
dist = _dist;
}
};
vector<Edge> edges;
vector<int> G[maxn];
ll d[maxn];
bool inq[maxn];
int p[maxn],tot;
int id[maxn][maxn];
ll w[maxn][maxn][2];//第一第二短的边
bool vis[maxn][maxn][maxn];//vis[src][i][j]以src为源点i->j为边是否在最短路树上
void Init(){
edges.clear();
for(int i = 0; i < maxn; i++)G[i].clear();
mem(id,-1);
}
void AddEdge(Edge e){
edges.pb(e);
tot = edges.size();
G[e.from].pb(tot-1);
}
void spfa(int s){
queue<int> Q;
mem(inq, false);
for(int i = 0; i < n; i++) d[i] = L,p[i] = i;
d[s] = 0;
inq[s] = true;
Q.push(s);
while(!Q.empty()){
int u = Q.front();Q.pop();
inq[u] = false;
for(int i = 0; i < G[u].size(); i++){
Edge &e = edges[G[u][i]];
if(d[u] < L && d[u] + e.dist < d[e.to]){
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if(!inq[e.to]){
inq[e.to] = true;
Q.push(e.to);
}
}
}
}
}
int main(){
// freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
while(cin >> n >> m >> L){
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
for(int k = 0; k < 2; k++)
w[i][j][k] = L;
for(int i = 0; i < m; i++){
int u, v;
ll di;
cin >> u >> v >> di;
u--;v--;
if(w[u][v][0] < di){
if(w[u][v][1] > di){
w[u][v][1] = di;
}
}
else{
w[u][v][1] = w[u][v][0];
w[u][v][0] = di;
}
w[v][u][0] = w[u][v][0];
w[v][u][1] = w[u][v][1];
}
Init();
for(int i = 0; i < n; i++)
{
for(int j = i+1; j < n; j++){
if(w[i][j][0] == L) continue;
AddEdge(Edge(i,j,w[i][j][0]));
id[i][j] = tot-1;
AddEdge(Edge(j,i,w[j][i][0]));
id[j][i] = tot-1;
}
}
ll c[maxn], c1 = 0LL, ans = 0LL;
mem(c,0);
mem(vis,false);
for(int i = 0; i < n; i++){
spfa(i);
for(int j = 0; j < n; j++)
c[i]+=d[j];
for(int j = 0; j < n; j++){
if(j != i){
int fa = edges[p[j]].from;
vis[i][fa][j] = vis[i][j][fa] = true;
}
}
ans+=c[i];
}
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)if(id[i][j] != -1){
Edge &e1 = edges[id[i][j]];
Edge &e2 = edges[id[j][i]];
e1.dist = w[e1.from][e1.to][1];
e2.dist = w[e2.from][e2.to][1];
ll temp = 0;
for(int src = 0; src < n; src++){
if(!vis[src][e1.from][e1.to]) temp+=c[src];
else{
spfa(src);
for(int j = 0; j < n; j++)
temp+=d[j];
}
}
c1 = max(c1, temp);
e1.dist = w[e1.from][e1.to][0];
e2.dist = w[e2.from][e2.to][0];
}
cout << ans << " " << c1 << "\n";
}
return 0;
}
The Toll! Revisited
原题大意
首先输入m条边。当经过小写字母时须要付一单位的过路费。当经过大写字母时，要付当前財务的1/20做过路费。
问在起点最少须要带多少物品使到达终点时还有k个物品。
当有多条符合条件的路径时输出字典序最小的一个。
算法分析
类似dij求最短路，已知终点的数量，倒着更新到起点，d[i]表示进入i节点后，至少要有d[i]的货物，注意边的起点终点不能一样
程序代码
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define ll long long
using namespace std;
const int maxn = 105;
#define INF (1LL<<61)
char id[maxn];
struct Edge{
int from, to;
Edge(int u, int v):from(u), to(v){}
};
struct HeapNode{
ll d;
int u;
bool operator < (const HeapNode& rhs)const{
if(d == rhs.d) return id[u] > id[rhs.u];
return d > rhs.d;
}
};
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
bool done[maxn];
ll d[maxn];
char p[maxn];
map<char, int> dict;
int flag[maxn];
void init(){
for(int i = 0; i < n; i++)G[i].clear();
edges.clear();
}
void AddEdge(int from, int to){
edges.push_back(Edge(from, to));
m = edges.size();
G[from].pb(m-1);
}
void dijkstra(int s, ll num){
priority_queue<HeapNode> Q;
for(int i = 0; i < n; i++) d[i] = INF;
for(int i = 0; i < maxn; i++) p[i] = 'z'+1;
d[s] = num;
mem(done,false);
Q.push((HeapNode){num, s});
while(!Q.empty()){
HeapNode x = Q.top(); Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = 0; i < G[u].size(); i++){
Edge &e = edges[G[u][i]];
int t = e.to;
if(flag[u] == 1){
if(d[t] >= d[u] + 1){
if(d[t] == d[u]+1 && p[t] > id[u]){
p[t] = id[u];
}
else if(d[t] > d[u] + 1){
d[t] = d[u] + 1;
p[t] = id[u];
}
Q.push({d[t], t});
}
}
else{
ll t1 = ceil(d[u] / 19.0*20.0);
if(d[t] >= t1){
if(d[t] == t1 && p[t] > id[u]){
p[t] = id[u];
}
else if(d[t] > t1){
d[t] = t1;
p[t] = id[u];
}
Q.push({d[t], t});
}
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int tot;
int kase = 0;
while(cin >> tot && tot != -1){
mem(flag,0);
dict.clear();
init();
n = 0;
for(int i = 0; i < tot; i++){
char f, t;
cin >> f >> t;
if(f == t) continue;
if(!dict.count(f)) dict[f] = n++, id[n-1] = f;
if(!dict.count(t)) dict[t] = n++, id[n-1] = t;
if(f >= 'a' && f <= 'z')
flag[dict[f]] = 1;
if(t >= 'a' && t <= 'z')
flag[dict[t]] = 1;
AddEdge(dict[f], dict[t]);
AddEdge(dict[t], dict[f]);
}
ll P;
char X, Y;
cin >> P >> X >> Y;
dijkstra(dict[Y], P);
vector<char> path;
char point = X;
path.pb(X);
while(p[dict[point]] != 'z' + 1){
path.pb(p[dict[point]]);
point = p[dict[point]];
}
printf("Case %d:\n", ++kase);
printf("%lld\n", d[dict[X]]);
for(int i = 0; i < path.size()-1; i++)
printf("%c-", path[i]);
printf("%c\n", path[path.size()-1]);
}
return 0;
}