Mar 20

SPOJ 15 - The Shortest Path[SHPATH]

Art of Science 0 Comments

题目就是要求最短路，我们根据数据规模采用Dijkstra+Heap的算法。这里C++如果使用STL中的堆是没有办法过的。

#include <cstdio>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 10000+5;

typedef pair<int,int> pii;
typedef pair<string,int> psi;
typedef vector<pii>::iterator iter;

vector<pii> road[MAXN];
vector<psi> city;
int n,dis[MAXN],size;
int heap[MAXN],hash[MAXN];

inline void trylo(int u) {
  int tmp = heap[u],i = u;
  while (i*2+1<size) {
    int j = i*2+1;
    if (dis[heap[j+1]]<dis[heap[j]]) j++;
    if (dis[heap[j]]<dis[tmp]) {
      heap[i] = heap[j];
      hash[heap[i]] = i;
      i = j;
    }
    else break;
  }
  heap[i] = tmp;
  hash[heap[i]] = i;
}

inline void tryhi(int u) {
  int tmp = heap[u],i = u;
  while (i>0) {
    int j = (i-1)/2;
    if (dis[tmp]<dis[heap[j]]) {
      heap[i] = heap[j];
      hash[heap[i]] = i;
      i = j;
    }
    else break;
  }
  heap[i] = tmp;
  hash[heap[i]] = i;
}

inline void push(int u) {
  heap[size] = u; hash[u] = size++;
  tryhi(size-1);
}

inline int htop() {
  int ret = heap[0];
  hash[heap[0]] = -1;
  heap[0] = heap[size-1];
  hash[heap[0]] = 0;
  size--;
  trylo(0);
  return ret;
}

int dijkstra(int x,int y) {
  memset(dis,127,sizeof(dis));
  dis[x] = 0;
  size = 0;
  memset(hash,-1,sizeof(hash));
  push(x);
  while (size) {
    int u = htop();
    for (iter i = road[u].begin(); i!=road[u].end(); ++i) {
      int v = i->second;
      if (dis[v]>dis[u]+i->first) {
        dis[v] = dis[u]+i->first;
        if (hash[v]==-1) push(v);
        else tryhi(hash[v]);
      }
    }
  }
  return dis[y];
}

int main() {
  int ncase;
  scanf("%d",&ncase);
  while (ncase--) {
    scanf("%d",&n);
    city.clear();
    for (int i = 0,m; i<n; i++) {
      char _name[16];
      scanf("%s%d",_name,&m);
      city.push_back(psi(string(_name),i));
      road[i].clear();
      for (int j = 0,t,c; j<m; j++) {
        scanf("%d%d",&t,&c); t--;
        road[i].push_back(pii(c,t));
      }
    }
    sort(city.begin(),city.end());
    int query;
    scanf("%d",&query);
    while (query--) {
      char _na[16],_nb[16];
      scanf("%s%s",_na,_nb);
      int ia = lower_bound(city.begin(),city.end(),psi(string(_na),0))->second;
      int ib = lower_bound(city.begin(),city.end(),psi(string(_nb),0))->second;
      printf("%d\n",dijkstra(ia,ib));
    }
  }
  return 0;
}

Your program in C++ from 2010-03-20 04:16:58 ran for 2.66 seconds and used 7020 KB of memory.

Feb 22

最小树形图

Art of Science 1 Comments

最小树形图就是最小生成树在带权有向图上面的变种，也就是在有向图上找出一个边权和最小的有向树。这个问题需要给定一个带权的有向图以及有向树的根节点v。所谓有向树是指除了叶节点以外，所有节点都有指向其孩子节点的有向边。专业一点的说，“有向树（Directed Tree）是一个用于定义数据流或流程的逻辑结构。数据流的源点是根。数据流是单向分支离开根部到达目标，这个目标就是有向树的叶子。”。

求解最小树形图的第一个算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法，该算法被称为朱-刘算法。在实现过程中，我们也可以表达为O(V3)的复杂度。

首先我们需要判断解是否存在。为了解决这个问题，我们只需要从指定的根节点v除法遍历一次就可以了。如果所有节点都可以被访问，那么解显然存在，否则不存在。另外，图中所有的自环也必须清除，因为这些自环显然不可能是最小树形图中的边。如果不知道什么是自环，请自行查阅图论相关定义。消除自环的目的是保证算法的时间复杂度。

下面是算法的流程：

  1. 对于图中除了根节点v以外的节点，选择一条权值最小的入边。所有被选择的边构成了一个子图，如果这个子图不含有有向环，那么这就是问题的解，算法结束；否则进行下一步。
  2. 我们需要收缩有向环，并且用一个新节点来代替。对于环中的点x，假定其选择边的权值为w0，y为环外的点，z为环收缩后新的节点。如果存在边<x,y>，那么<z,y>的边权值与<x,y>相同。如果存在边<y,x>且权值为w，那么新边<y,z>的权值就是w-w0。
  3. 重复执行1、2两个步骤。

要保证算法O(VE)的复杂度，要做到找最小入边O(E)，找环O(V)，收缩O(E)。再加上由于收缩环最多只进行V-1次（自环已经被消除），所以时间复杂度为O(VE)。在步骤2中，x的出边权值不变是因为收缩环并没有影响边所指向的节点，而入边的权值之所以要变小，是因为当新边被选择之后，x原来选择的入边就会被取消选择，所以实际花费的代价就是w-w0。

以下是2道可以提交的题目。

  • [UVa]11183 - Teen Girl Squad
  • [PKU]3164 - Command Network
Feb 3

最短增广路在网络流中的应用

Art of Science 0 Comments

最短增广路，顾名思义，就是一条增广路，而且还是所有增广路中最短的一条。要求出最短增广路也十分容易，只要在残量网络中求出源点到汇点的最短路就可以了（所有边的长度为1）。

求出了最短增广路，我们就可以沿着它对网络进行增广，而且可以证明，如果只要求最大流，最多经过n（n为总结点数）次增广，就可以求出最大流。实现也非常简单，由于所有边的长度为1，所以只需要使用宽搜。使用最短增广路的方法求最大流，其实也是Ford-Fulkerson方法的一种，这种方法的特点是每次找出一条残量网络中的增广路径并进行增广。整个过程中满足流的网络的三个性质：容量限制、反对称性、流守恒性。

如果不知道什么是残量网络（或者又被叫做残留网络），请看下面的解释。

  • 残量：容量－流量。
  • 残留边：有残留容量的边成为残留边
  •  残留网络：由网络的点集、残留边集构成残留网络。

这里我们需要注意一点，宽搜的结果如果可以为后面所利用的话，我们就可以写出一种新的求最大流的算法：SAP，全称Shortest Augmenting Path Algorithm。其时间复杂度为O(n2m)。在实践中，这种算法效率还是比较高的，而且性价比相当好（我一般都会使用它）。

在SAP中，定义每个点的距离标号，即残留网络中点到汇点的距离。然后，只需要在距离标号相邻的点间寻找增广路径。如果从一个点出发没有可行边，就对该点进行重标记，然后并回溯（类似预流推进算法）。

可行边就是说，存在一条边<i,j>，当且仅当ri,j>0且di=dj+1时，边是容许边，我们的算法只考虑容许边（这里d指距离标号，r指残量网络中的流量）。

算法的一开始，我们从汇点t进行一次宽搜求出距离标号（或者也可以不进行预处理，直接赋值为0，因为随着重标记的过程，距离标号会自行调整），然后从源点s开始递归操作（或者也可以不递归，因为算法本身并不繁琐）。对于一个点i，如果存在容许边<i,j>，当j是汇点时增广并从源点开始递归，否则就令i是j的前驱，并递归j。否则对i重标号，使得di=min{dj|ri,j>0}+1，并回溯。当$d_s\geq n$时算法停止，此时不存在任何一条增广路。

当然我们可以参考预流推进，对它进行间隙优化。同时还有一个叫做当前弧的优化，采用后速度也有一定的提升。而且，采用前向星的储存方式会更好。

我们也可以用最短增广路来求最小费用最大流，原理不需要再阐述了，如果是用增广路算法来求最小费用最大流，就是要找一条费用最少的路径来进行增广。当然可以套用最短增广路的方法来做。 

Feb 2

二分图最大权完美匹配的KM算法

Art of Science 0 Comments

 二分图最大权完美匹配KM算法是在一个二分图里，求一个最大权匹配，但是要求这个匹配必须是完美匹配。如果匹配不一定是完美匹配，那么似乎只能将其转化为最小费用最大流来做了。我们可以使用KM算法对任意带权（无论正负权）二分图求最大/最小权完美匹配，它的算法复杂度是O(n3)，但是如果写得不好会变成O(n4)。

KM算法是通过给每个顶点一个标号（我们有时称之为顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。我们令二分图中X部的节点的顶标为Ai，Y部的节点的顶标为Bi。X部与Y部节点之间的权值为Wi,j，那么，在算法进行的过程中，我们必须始终保持$A_i+B_i\geq W_{i,j}$成立。因为KM算法的正确性基于以下定理：

若由二分图中所有满足Ai+Bi=Wi,j的边 (i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。

初始时为了使$A_i+B_i\geq W_{i,j}$成立，令Ai为所有与Xi顶点关联的边的权值的最大值，令Bi=0。如果当前的相等子图没有完备匹配，就需要修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止（这样就可以求出最大权匹配）。

如果当前相等子图找不到完备匹配，那么是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，现在我们把交错树中X部的顶点的顶标全都减小某个值d，Y部的顶点的顶标全都增加d，就可以使得至少有一条新边进入相等子图。这里d=min{Ai+Bi-Wi,j}，而且Xi在交错树中，Yi不在。

但是如果仅仅是这样，用朴素的方法实现，算法复杂度是O(n4)。我们给每个Y部的顶点一个“松弛量”slack，每次开始找增广路时松弛量初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slackj变成原值与Ai+Bi-Wi,j的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slackj值都减去d。经过这样一个优化实现后，算法复杂度就变成了O(n3)。 

Jan 18

求强连通分量的三种算法——Kosaraju, Tarjan, Gabow

Art of Science 1 Comments

就我所知，有三种时间复杂度为O(n)的方法可以求强连通分量，分别是Kosaraju、Tarjan和Gabow。

  1. Kosaraju
    算法的步骤为
    • 对图G进行DFS，并按照遍历完成的先后顺序进行标号。
    • 将图G中所有的边反向得到G'。
    • 对G'进行DFS，每轮DFS都选择编号最大的点最为当前的遍历树的根。
    • 最后，遍历得到的森林就是SCC的集合。
    该算法的优点在于，最后得到的节点是按照拓扑序组织好的，在求解2-SAT的过程中十分方便。
  2. Tarjan
    第一个求解SCC的算法，应用非常广泛，几乎任何和图的遍历有关的问题都可以套用Tarjan算法的思想（比如，求割点、桥、块等等）。
    在遍历时，对每一个节点定义时间戳，同时定义Low函数，含义为节点及其子孙通过非父子边的返祖边所能到达的最小时间戳。最后若Low函数等于其时间戳，则当前递归栈内存在一个SCC。
    代码如下：
    void dfs(int index) {
  low[index] = dfn[index] = cnt++;
  used[index] = 1;
  del[index] = 0;
  st[top++] = index;
  for (int i = last[index]; i!=-1; i = e[i].nxt)
    if (!used[e[i].y]) {
      dfs(e[i].y);
      if (low[index]>low[e[i].y]) low[index] = low[e[i].y];
    }
    else if (!del[e[i].y]) if (low[index]>dfn[e[i].y])
      low[index] = dfn[e[i].y];
  if (low[index]==dfn[index]) {
    do {
      root[st[--top]] = index;
      del[st[top]] = 1;
    } while (st[top]!=index);
  }
}
  3. Gabow
    算法的原理说起来太麻烦，还是直接给出代码。其实这个算法并不是很常用。
    #include <cstdio>
#include <cstring>
#include <stack>

using namespace std;

const int MAXN = 1000;

struct node {
  int tar;
  node *nxt;
  node(int _tar,node *_nxt)
    : tar(_tar),nxt(_nxt) {}
};

node *g[MAXN];
int n,m,co,all,dfn[MAXN],id[MAXN];
stack<int> vec,path;

void dfs(int x) {
  dfn[x] = co++;
  vec.push(x);
  path.push(x);
  for (node *i = g[x]; i!=NULL; i = i->nxt)
    if (dfn[i->tar]==-1) dfs(i->tar);
    else if (id[i->tar]==-1)
      while (dfn[path.top()]>dfn[i->tar]) path.pop();
  if (path.top()==x) path.pop();
  else return;
  for (int i; ;) {
    id[i = vec.top()] = all;
    vec.pop();
    if (i==x) break;
  }
  all++;
}

int main() {
  freopen("gabow.in","r",stdin);
  freopen("gabow.out","w",stdout);
  scanf("%d%d",&n,&m);
  memset(g,0,sizeof(g));
  for (int i = 0,a,b; i<m; i++) {
    scanf("%d%d",&a,&b); a--; b--;
    g[a] = new node(b,g[a]);
  }
  co = all = 0;
  memset(dfn,-1,sizeof(dfn));
  memset(id,-1,sizeof(id));
  for (int i = 0; i<n; i++)
    if (dfn[i]==-1) dfs(i);
  for (int i = 0; i<n; i++)
    printf("%d\n",id[i]);
  return 0;
}