标签归档:最短路

Shortest Paths in Grid Graphs

1. Shortest Path Problem

The shortest path problem is one of the most important and fundamental problems in graph theory. It has many real-world applications, such as finding the best driving directions and finding the minimum delay route in networking.

There are mainly two variants of the problem: single-source shortest paths (SSSP) and all-pair shortest paths (APSP). The most famous algorithms for SSSP are Bellman-Ford (applicable to arbitrary weights, $O(VE)$) and Dijkstra’s (applicable to nonnegative weights,$O(V \log V+E)$); the best-known algorithms for APSP are Floyd’s in $O(V^3)$ time and Johnson’s in $O(V^2 \log V + VE)$ time, which are both applicable to arbitrary weights; for nonnegative weights, running $V$ rounds of Dijkstra’s algorithm is fine.

2. Grid Graph

Formally speaking, a grid graph $P_w \times P_h$ is the Cartesian product of two paths. A grid graph can be drawn in a plane as a lattice. The following figure shows a grid graph $P_5 \times P_4$. Note that the weights of the edges are omitted.

We consider the shortest path problem in grid graphs, where edges are undirected and nonnegatively weighted. Specifically, we can preprocess the graph, and then answer several queries online. Each query contains two vertices $u, v$, which asks the shortest path between $u$ and $v$. Let $n = w \times h$ denote the size of the graph $P_w \times P_h$.

One naive solution is to do nothing in preprocessing, and for each query, just run an SSSP (e.g., Dijkstra’s). The time complexity is $O(1)/O(n \log n)$.

Another solution is to compute APSP during preprocessing. If we simply run $n$ rounds of SSSP algorithm, the time complexity is $O(n^2 \log n) / O(1)$.

Here, we present a nice algorithm that achieves $O(\sqrt{n})$ time per query after $O(n^{1.5} \log n)$ preprocessing. Compared with the above naive algorithms, the $O(n^{1.5} \log n) / O(\sqrt{n})$ algorithm features a good space-time tradeoff. The basic idea is divide and conquer.

3. The Algorithm

Assume w.l.o.g. that $w \geq h$. Also we use ordered pair $(x, y)$ $(1 \leq x \leq w, 1 \leq y \leq h)$ to represent a vertex in $P_w \times P_h$.

We define the midline of the graph as the vertices in the $\frac{w}{2}$th column. This is how we divide subproblems. Now we solve the queries where two vertices lie on different sides of the midline. Given to vertices $u, v$ where $u$ is in the left of the midline and $v$ is in the right of the midline, then every path between $u$ and $v$ must cross the midline, though it may cross the line left and right multiple times (as the following figure shows).

Now comes the key point. For the sake of convenience we denote the vertices in the midline as $M_i$, i.e. $M_i = (\frac{w}{2}, i)$. For every vertex in midline $M_i$, run an SSSP in preprocessing stage, and stores its distance to every other vertex. How does this information help? Consider a vertex $u$ left to the midline and a vertex $v$ right to the midline, since the shortest path between them must cross the midline, we can try all vertices in the midline, and simply pick the shortest path:
$$ d(u, v) = \min_{1 \leq i \leq h} d(u, M_i) + d(M_i, v). $$
Since $w \geq h$, there are at most $\sqrt{n}$ vertices in the midline, so the preprocessing time is $O(\sqrt{n} \cdot n \log n)$, and the time per query is $O(\sqrt{n})$.

How should we answer the queries where two vertices lie on the same side of the midline? Note that we can’t simply solve the problem on the subgraph left to the midline, since the shortest path might possibly, though not necessarily, cross the midline.

But this is never a problem. We can update $d(u, v)$ with $\min_{1 \leq i \leq h} d(u, M_i) + d(M_i, v)$ for each query $(u, v)$ not cross the midline, then recursively solve the problem on the left and right subgraphs.

The total preprocessing time follows this recursion:
$$ T(n) = 2T(n / 2) + O(n^{1.5} \log n). $$
By the master theorem, $T(n) = O(n^{1.5} \log n)$.

4. Remarks

From the view of implementation, the $O(\sqrt{n})$ query time can be done very efficiently, since it just computes the minimum component of the sum of two vectors. This is SIMD- and cache-friendly. Also, since in preprocessing stage we need to run $h$ independent rounds of SSSP algorithm, the preprocessing part can be easily parallelized.

Nordic Collegiate Programming Contest 2018 [NCPC2018] 题解

A. Altruistic Amphibians

unsolved

B. Baby Bites

solved (0:08, +1)

逐个检查即可。

C. Code Cleanups

solved (0:17)

逐日模拟即可。

D. Delivery Delays

solved (4:55)

首先跑最短路获取APSP。

二分答案,然后dp出送完前i单最早时间,或者不可行

E. Explosion Exploit

solved (3:23)

可以用dp的思想转移。由于随从的顺序无关,可以将他们的血量排序,总状态数会大大减少。

F. Firing the Phaser

unsolved

G. Game Scheduling

unsolved

H. House Lawn

solved (0:34)

如果$\frac{10080rc}{t+r} \geq l$,则说明可行。记录可行的机器中,最便宜的那些机器的名称即可。

I. House Lawn

solved (1:00 +1)

由于相邻两数相差至少为一倍,只需要从大到小排序,然后能减就减。最后结果为0,则选中的那些就是答案。

J. Jumbled String

solved (1:57 +2)

可以根据00和11子序列的数量算出0和1的数量,然后根据01和10子序列的数量调整0和1的位置。注意若干边界情况。

K. King’s Colors

solved (3:07)

用最多k种颜色染色有$(k-1)^{n-1}k$种方案。用恰好$k$种颜色的方案数可以用容斥算出。

 

2016 China Collegiate Programming Contest Final 题解

题面:http://codeforces.com/gym/101206/attachments/download/5010/ccpc-20162017-finals-en.pdf

(更新中)

Problem A. The Third Cup is Free

有n杯咖啡,每三杯咖啡中最便宜的那杯可以免单,求最小花费。

题解

签到题。从大到小排好序后,每三个免一个即可。

代码:(by Roundgod)

#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int t,n,a[MAXN];
int main()
{
    scanf("%d",&t);
    int kase=0;
    while(t--)
    {
        kase++;
        printf("Case #%d: ",kase);
        scanf("%d",&n);
        int sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sort(a,a+n);
        for(int i=n-3;i>=0;i-=3)
            sum-=a[i];
        printf("%d\n",sum);
    }
    return 0;
}


Problem B. Wash

给定L件脏衣服,N台洗衣机,D台烘干机。第i台洗衣机要花Wi时间洗一件脏衣服,第j台烘干机要花Dj时间烘干一件衣服。衣服必须先洗完再烘干。所有机器可以并行工作。问洗完并烘干所有衣服要多少时间。

数据范围:$1 \leq L \leq 10^6, 1 \leq N, M \leq 10^5, 1 \leq W_i, D_i \leq 10^9 $

题解

我们先考虑只洗衣服该如何安排。显然每台洗衣机中间不会停止工作,否则我们将后面的任务向前移动,不会得到一个更差的解。这样,第i台洗衣机洗完地j件衣服的时间就是$w_{ij} = jW_{i}$。只要选取前L小的$T_{ij}$即可。为便于实现,可用优先队列。

同理,可处理出前L小的$d_{ij}$烘干时间。下面我们就是要求一个$w_{ij}$和$d_{ij}$的完美匹配,使得对应的$w_{ij}$和$d_{ij}$的和的最大值最小。这只需要将$w_{ij}$正向排序,$d_{ij}$反向排序,然后一一匹配即可。容易证明,这样匹配一定是最优的。

代码:(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int l, n, m;
LL w[100006], d[100006];
LL t1[1000006], t2[1000006];

typedef pair<LL, int> p;

int main() {
  int T; scanf("%d", &T);
  Rep (t, T) {
    priority_queue<p, vector<p>, greater<p> > q1, q2;
    scanf("%d%d%d", &l, &n, &m);
    rep (i, n) {
      int a; scanf("%d", &a);
      w[i] = a;
      q1.push({w[i], i});
    }
    rep (i, m) {
      int a; scanf("%d", &a);
      d[i] = a;
      q2.push({d[i], i});
    }
    rep (i, l) {
      LL val; int id;
      tie(val, id) = q1.top(); q1.pop();
      _debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
      t1[i] = val;
      q1.push({val+w[id], id});
    }
    rep (i, l) {
      LL val; int id;
      tie(val, id) = q2.top(); q2.pop();
      _debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
      t2[l-1-i] = val;
      q2.push({val+d[id], id});
    }
    LL ans = 0;
    rep (i, l) {
      ans = max(ans, t1[i] + t2[i]);
    }
    cout << "Case #" << t << ": " << ans << endl;
  }
  return 0;
}


Problem C. Mr. Panda and Survey


Problem D. Game Leader


Problem E. Problem Buyer


Problem F. Periodical Cicadas


Problem G. Pandaland

给出一个4000个点的带权无向图,求图中的最小权环。

题解

枚举所有边,删去该边后,求这条边两点间的最短路,然后加上该边的权值,取最小值即可。

注意,当图中不含圈时,要输出0(而不是-1)(补题的时候因为这个原因WA了5发,qaq…

代码:(by aequa)

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
    __func__, ##__VA_ARGS__)
#else 
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

#define int LL
#undef INT_MAX
#define INT_MAX LLONG_MAX

typedef pair<int, int> pt;


struct Sol {
  int n = 0;
  map<pt, int> mp;
  vector<pair<int, int>> edges;
  vector<vector<int>> adj;

  int getID(int x, int y) {
    auto ptr = mp.find({x, y});
    if (ptr != mp.end()) return ptr->second;
    mp[{x, y}] = n;
    adj.push_back({});
    return n++;
  }
  
  int ans = INT_MAX / 2;
  int d[10000];
  bool done[10000];

  void dijkstra(int src) {
    priority_queue<pt, vector<pt>, greater<pt>> q;

    fill(d, d+n, INT_MAX / 2);
    d[src] = 0;
    fill(done, done+n, false);
    q.push({0, src});
    while (q.size()) {
      int u = q.top().second; q.pop();
      if (done[u]) continue;
      done[u] = 1;
      for (int id : adj[u]) {
        int v, w; tie(v, w) = edges[id];
        if (d[v] > d[u] + w) {
          d[v] = d[u] + w;
          if (d[v] < ans) q.push({d[v], v});
        }
      }
    }
  }

  Sol(int t) {
    int m; cin >> m;
    edges.resize(m+m);
    rep (i, m) {
      int x1, y1, x2, y2, w;
      int id1, id2;
      cin >> x1 >> y1 >> x2 >> y2 >> w;
      id1 = getID(x1, y1); id2 = getID(x2, y2);
      edges[i<<1] = {id2, w};
      edges[i<<1|1] = {id1, w};
      adj[id1].push_back(i<<1);
      adj[id2].push_back(i<<1|1);
    }
    rep (u, n) {
      for (int id : adj[u]) {
        int v, w;
        tie(v, w) = edges[id];
        edges[id].second = edges[id^1].second = INT_MAX / 2;
        dijkstra(u);
        ans = min(ans, d[v] + w);
        edges[id].second = edges[id^1].second = w;
      }
    }
    if (ans >= INT_MAX / 2) ans = 0;
    cout << "Case #" << t << ": " << ans << endl;
  }
};

int32_t main() {
  int T; cin >> T;
  Rep (t, T) {
    Sol sol(t);
  }
  return 0;
}

 


Problem H. Engineer Assignment


Problem I. Mr. Panda and Crystal

有N种宝石,每种宝石有一些价值。有些宝石可以直接由法力值合成。此外,还存在K种合成方案,可以利用若干已有的宝石合成新的宝石。给定初始的法力值M,求能够合成的宝石的价值的最大值。

数据范围:$1 \leq M \leq 10000, 1 \leq N \leq 200, 1 \leq K \leq 200$

题解

背包的变形题。本题主要的问题是,一种宝石可能有多种获得方法,除了可以直接用法力值合成外,还有可能存在多种合成该宝石的方案。我们希望预处理出来(直接或间接)获得该种宝石的最小法力值消耗。由于更新一种宝石的最小法力值消耗可能会影响其他宝石的最小法力值消耗,这很像最短路中更新某个节点的距离会影响其他节点的距离,因此可以采用Bellman-Ford算法,迭代更新直到无法更新为止。显然这么做的复杂度是$N^2K$的。预处理出来后,直接套多重背包即可。

代码:(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int m, n, k;
LL c[256], v[256];

vector<int> dep[205];
//   id                id  cnt
pair<int, vector<pair<int, int>>> formula[205];

bool flag = false;

void update(int i) {
  LL tot = 0;
  int id = formula[i].first;
  for (auto& item : formula[i].second) {
    tot += c[item.first] * item.second;
  }
  if (tot < c[id]) {
    _debug("update %d!", formula[i].first);
    c[formula[i].first] = tot;
    flag = true;
  }
}

LL dp[10005];

int main() {
  int T; scanf("%d", &T);
  Rep (t, T) {
    scanf("%d%d%d", &m, &n, &k);
    Rep (i, n) {
      int tp; scanf("%d", &tp);
      int co = INT_MAX, va = 0;
      if (tp == 0) {
        scanf("%d", &va);
      } else {
        scanf("%d%d", &co, &va);
      }
      c[i] = co;
      v[i] = va;
    }
    _debug("!");
    rep (i, k) {
      int x, y;
      scanf("%d%d", &x, &y);
      formula[i].first = x;
      formula[i].second.resize(y);
      rep (j, y) {
        int u, v;
        scanf("%d%d", &u, &v);
        formula[i].second[j] = {u, v};
      }
    }
    _debug("!");
    do { // bellman-ford
      flag =  false;
      rep (i, k) update(i);
    } while (flag);
    memset(dp, 0, sizeof dp);
    Rep (i, n) {
      for (int w = c[i]; w <= m; w++) {
        dp[w] = max(dp[w], dp[w - c[i]] + v[i]);
      }
    }
    printf("Case #%d: %d\n", t, int(dp[m]));
  }
  return 0;
}


Problem J. Worried School


Problem K. Lazors

神仙题。


Problem L. Daylight Saving Time

每年的三月的第二个星期日的2点整,将时间拨快1小时,进入夏令时(PST);每年的十一月的第一个星期日的2点整,将时间拨慢1小时,进入标准时(PDT)。给一个日期和时间,判断该时间是PST,PDT,两者都有可能或是两者都不可能。时间在2007-01-01 00:00:00和2100-12-31 23:59:59之间。

题解

只要预处理出每一天的类型(一定是PST,一定是PDT,从PST变换为PDT,从PDT变换为PST),然后分情况讨论即可。

实现的时候要注意处理闰年的情况。除2100年外,年数是4的倍数就是闰年。

代码:(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long ull;

enum {
  A, B, C, D
};

const int  mday[13] = { 0,
  31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};

int type = A;
int yy = 2007, mm = 1, dd = 1;
int wday = 1;

bool isleap(int y) {
  if (y % 4 == 0  && y != 2100) return true;
  return false;
}

void adv_year() {
  yy++;
}

void adv_month() {
  mm++;
  if (mm > 12) {
    mm = 1;
    adv_year();
  }
}

int advan() {
  dd++;
  wday ++;
  if (wday > 7) wday = 1;
  int mmday = mday[mm];
  if (mm == 2 && isleap(yy)) mmday++;
  if (dd > mmday) {
    dd = 1;
    adv_month();
  }
  if (mm == 3 && wday == 7 && dd > 7 && dd <= 14) {
    type = C;
    return B; 
  }
  if (mm == 11 && wday == 7 && dd <= 7) {
    type = A;
    return D;
  }
  return type;
}

string genstr() {
  char buf[100];
  sprintf(buf, "%04d-%02d-%02d", yy, mm, dd);
  return string(buf);
}

map<string, int> m;

void prep() {
  m[genstr()] = type;
  do {
    int tp = advan();
    m[genstr()] = tp;

  } while (yy <= 2100);
}


int main() {
  prep();
  string str;
  char tim[20];
  int hh;
  int T;
  cin >> T;
  Rep(t, T) {
    cin >> str >> tim;
    sscanf(tim, "%d", &hh);
    switch (m[str]) {
      case A:
        printf("Case #%d: PST\n", t);
        break;
      case B:
        if (hh < 2) {
          printf("Case #%d: PST\n", t);
        } else if (hh >= 3) {
          printf("Case #%d: PDT\n", t);
        } else {
          printf("Case #%d: Neither\n", t);
        } 
        break;
      case C:
        printf("Case #%d: PDT\n", t);
        break;
      case D:
        if (hh < 1) {
          printf("Case #%d: PDT\n", t);
        } else if (hh >= 2) {
          printf("Case #%d: PST\n", t);
        } else {
          printf("Case #%d: Both\n", t);
        } 
        break;
    }
  }
  return 0;
}

2017-2018年问题求解(三)期末上机考试 Day2 题解

C. 花椰菜与西兰花

题意:有一块菜地,被分成 $latex n \times m$ 格,每格被种上花椰菜、西兰花或什么都不种。现在要在格子之间建一些篱笆,使得被篱笆分隔出来的每一连通区域中,至多只有一种作物。问篱笆的总长度最少是多少。

数据范围:$latex 1 \leq n \leq 50, 1 \leq m \leq 1000$

题解:最小割还是挺明显的。源点到所有花椰菜连上无穷容量边,所有西兰花到汇点连无穷容量边,然后相邻两个区域连容量为 1 的双向边。根据 MFMC 定理,答案就是从源点到汇点的最大流。

D. 旅游路线

题意:有 $latex n$ 个区域,每个区域内有 $latex s_i$ 个车站。区域内的车站之间移动需花费 $latex k_i$ 时间;此外,还有 $latex m$ 辆班车来回于两个车站之间,并需要花费 $latex c_j$ 代价。问从 1 号区域的第 1 个车站到 $latex n$ 号区域至少需要花费多少时间。

数据范围:

  • 部分数据满足 $latex 1≤n≤20, 1≤m≤100, 1≤s_i≤5, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤1000, 1≤m≤50000, 1≤s_i≤200, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤30000, 1≤m≤2*10^5, s_i=1, 1≤k_i, c≤1000$;
  • 部分数据满足 $latex 1≤n≤5000, 1≤m≤2*10^5, 1≤s_i≤50, 1≤k_i, c≤1000$。

题解:最短路,但是裸的 Dijkstra 肯定是过不了的。这是因为区域内暴力连边的话,会形成完全图,导致边数爆炸。为此,可以为每个区域设置一个特殊节点,该节点可以表示从区域内任何一个节点出发。这样,每个区域内的点都可以连一条长度为 $latex k_i$ 的单向边到该特殊节点,此外,从该区域中的某一点出发的边,同样也可以从特殊节点出发。这样整个图中只有 $latex m + \sum s_i $ 条边,跑 Dijkstra 就不会T了。