Beyond the Void
BYVoid
USACO MAR08 Gold Cow Jogging 牛跑步
本文正體字版由OpenCC轉換

這是一個K短路徑問題,解決方法有Yen算法等等。但是這並不是一個一般的K短路徑問題,這是一個有向無環圖。所以可以考慮動態規劃(記憶化搜索)的思想解決。

記頂點i到目標點N的k短路徑的長度爲Dis[i,k]。可以知道每個頂點Dis[i,*],都是由大於i的頂點j,Dis[j,*]推得的。由於源點和目標都是確定的,我們可以從目標節點倒推回源點。

建立原圖的逆向圖,即從1開始到N。記從頂點1到i的當前路徑的長度爲S,訪問頂點i鄰接的頂點j,令新的到j的路徑長度F爲S+ (i,j)。把F加入到Dis[j]中,並只保留前K小的。然後訪問頂點j。如果F大於所有Dis[j],則不能用該路徑鬆弛頂點j,不訪問j。當全部訪問完以後,按照要求輸出Dis[N]即可。

對於維護Dis[i],可以使用堆、甚至平衡樹等高級數據結構。但是考慮到K並不是很大,維護一個數組即可。當插入新的元素V時,如果已有的數目不足K,直接插入;如果已經爲K,在這K個元素中找到最大值Max,如果V<Max,用V替換Max;如果V>=Max,不必插入。

時間複雜度爲O(M*K)

/*
ID: cmykrgb1
PROG: cowjog
LANG: C++
*/
#include <iostream>
#define MAX 1001
#define MAXK 101
#define INF 0x7fffffff

using namespace std;

class list
{
public:
	list *next;
	int p,v;
	list(int tp,int tv)
	{
		p=tp;
		v=tv;
		next=0;
	}
};

class tadjl
{
public:
	list *first,*last;
	tadjl()
	{
		first=last=0;
	}
	void ins(int p,int v)
	{
		if (first)
			last=last->next=new list(p,v);
		else
			first=last=new list(p,v);
	}
};

class monotony
{
public:
	int Size,cnt;
	int C[MAXK];
	monotony(int K)
	{
		Size=K;
		cnt=0;
	}
	bool ins(int v)
	{
		int i,j,max=0;
		if (cnt<Size)
		{
			C[cnt++]=v;
		}
		else
		{
			for (i=0;i<cnt;i++)
			{
				if (C[i]>max)
				{
					max=C[i];
					j=i;
				}
			}
			if (v>=max)
				return false;
			C[j]=v;
		}
		return true;
	}
};

int N,M,K;
tadjl adjl[MAX];
monotony *Dis[MAX];

void init()
{
	int i,a,b,v;
	freopen("cowjog.in","r",stdin);
	freopen("cowjog.out","w",stdout);
	cin >> N >> M >> K;
	for (i=1;i<=M;i++)
	{
		cin >> a >> b >> v;
		adjl[b].ins(a,v);
	}
	for (i=1;i<=N;i++)
	{
		Dis[i]=new monotony(K);
	}
	for (i=0;i<K;i++)
	{
		Dis[N]->C[i]=INF;
	}
}

void dfs(int i,int S)
{
	int j,v,F;
	bool succ;
	list *k;
	for (k=adjl[i].first;k;k=k->next)
	{
		j=k->p;
		v=k->v;
		F=v+S;
		succ=Dis[j]->ins(F);
		if (succ && j!=N)
		{
			dfs(j,F);
		}
	}
}

inline int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}

void print()
{
	int i;
	qsort(Dis[N]->C,K,sizeof(Dis[N]->C[0]),cmp);
	for (i=0;i<K;i++)
	{
		if (Dis[N]->C[i]!=INF)
			cout << Dis[N]->C[i];
		else
			cout << -1;
		cout << endl;
	}
}

int main()
{
	init();
	dfs(1,0);
	print();
	return 0;
}

官方題解

參考翻譯

翻譯By BYVoid

我們正在考慮的一個無環圖,我們希望找到的K ≤ 100最短路徑。由於圖是環自然有序的頂點,動態規劃是一個很好的第一種辦法。

假設我們知道頂點i到穀倉頂點N的K短路徑,我們可以用來計算從頂點i - 1到N的K短路徑。我們認爲所有從頂點的i - 1 的出邊。假設頂點的i - 1有d個出邊,這d個出邊的末端頂點都大於的i - 1,我們可以從每個這些頂點計算K短路徑。

考慮將要計算的頂點的i - 1至所有這些d * K條路徑,頂點i - 1到N的K短路徑頂將來自與這些d * K條路徑。我們可以通過合併這些d列表中項目,有效地維護一個列表,存儲從i-1到N的K短路徑。在每一個頂點需要d * K的時間。計算所有的頂點爲O(MK)時間。既然M = 10000和K = 100,這將是約1000000個操作。

原文

We are given an acyclic graph and we wish to find the K ≤ 100 shortest paths. Since the graph is acyclic with a natural ordering to the vertices, Dynamic Programming is a good first approach.

Suppose that we knew the K shortest paths starting at each vertex i for i ≥ l and going downhill to the barn at vertex N. Then, to compute the K shortest such paths beginning at vertex i-1, we consider all outgoing edges from vertex i-1. Suppose that vertex i-1 has d outgoing edges. The ends of these d edges are all larger than i-1 and we have computed the K shortest paths from each of these. We can consider prepending vertex i-1 to all of these dK paths. The best K paths starting at vertex i-1 will come from these dK paths. We can efficiently compute a sorted list of the K best paths starting at vertex i-1 by merging these d lists of K items. This requires d*K time at each vertex. Summing over all vertices yields O(MK) time. With M=10,000 and K=100, this will be around 1,000,000 operations, which works. 官方程序

#include <stdio.h>
 
const int BIG = 1000000000;
 
const int MAXN = 2000;
const int MAXE = 20000;
const int MAXK = 200;
 
int n,e,k;
int ea[MAXE];
int eb[MAXE];
int elen[MAXE];
int d[MAXN];
int *out[MAXN];
int *len[MAXN];
int path[MAXN][MAXK];
 
int ei[MAXN];
 
int main() {
 
  FILE *fin;
 
  fin = fopen("cowjog.in", "r");
  fscanf(fin, "%d %d %d", &n, &e, &k);
  for(int i = 0; i < n; ++i){
    d[i] = 0;
  }
  for(int i = 0; i < e; ++i){
    int a,b,l;
    fscanf(fin, "%d %d %d", &b, &a, &l);
    --a; --b;
    ++d[a];
  }
  fclose(fin);
 
  out[0] = &eb[0];
  len[0] = &elen[0];
  for(int i = 1; i < n; ++i){
    out[i] = out[i-1] + d[i-1];
    len[i] = len[i-1] + d[i-1];
  }
 
  fin = fopen("cowjog.in", "r");
  fscanf(fin, "%d %d %d", &n, &e, &k);
  for(int i = 0; i < n; ++i){
    d[i] = 0;
  }
  for(int i = 0; i < e; ++i){
    int a,b,l;
    fscanf(fin, "%d %d %d", &b, &a, &l);
    --a; --b;
    out[a][d[a]] = b;
    len[a][d[a]] = l;
    ++d[a];
  }
  fclose(fin);
 
 
  path[n-1][0] = 0;
  for(int i = 1; i < k; ++i){
    path[n-1][i] = BIG;
  }
 
  for(int i = n-2; i >= 0; --i){
    for(int j = 0; j < d[i]; ++j){
      ei[j] = 0;
    }
    for(int j = 0; j < k; ++j){
      int best_m = 0;
      int best_d = BIG;
      for(int m = 0; m < d[i]; ++m){
	if(len[i][m] + path[out[i][m]][ei[m]] < best_d) {
	  best_m = m;
	  best_d = len[i][m] + path[out[i][m]][ei[m]];
	}
      }
      path[i][j] = best_d;
      ++ei[best_m];
    }
  }
 
  FILE *fout = fopen("cowjog.out", "w");
  for(int i = 0; i < k; ++i){
    fprintf(fout, "%dn", (path[0][i] == BIG) ? -1 : path[0][i]);
  }
  fclose(fout);
 
 
  return(0);
}

上次修改時間 2017-05-22

相關日誌