3114.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3114  User Id:fzk 
Memory:2996K  Time:203MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;
class Graph {

public:

	enum { MAX_NUM_EDGE = 500010, MAX_NUM_NODE = 510 };
	
	struct Edge {
		int to;
		int dis;
		Edge *next;
	}e[2*MAX_NUM_EDGE];
	
	Edge *e_begin[MAX_NUM_NODE], *e_end[MAX_NUM_NODE], *e_reverse[MAX_NUM_NODE];
	Edge *e_reduced[MAX_NUM_NODE];
	int flag[MAX_NUM_NODE];

	void init( );
	void insertEdge( int form, int to, int len );
	
	int Strongly_Connected_Component( int n, bool reduce = false );

private:
	int sign[MAX_NUM_NODE], count;
	int *dis[MAX_NUM_NODE];
	int en, n;
	int st[MAX_NUM_NODE], sn;
	bool reduce;
	//简化边表
	void Reduced( int m );
	//两次DFS
	void DFS( int k );
	void RDFS( int k );

};

///////////////////////////////////////////////////////
//函数实现

void Graph::init( ) {
	n = en = 0;
	memset( e_begin, 0, sizeof e_begin );
	memset( e_reverse, 0, sizeof e_reverse );
	memset( e_end, 0, sizeof e_end );
}

void Graph::insertEdge( int from, int to, int len ) {
	//插入边
	e[en].to = to;
	e[en].next = e_begin[from];
	e[en].dis = len;
	e_begin[from] = &e[en];
	//修改边表结尾
	if( e_end[from] == 0 )
		e_end[from] = &e[en];
	en++;
	//插入逆向边
	e[en].to = from;
	e[en].next = e_reverse[to];
	e[en].dis = len;
	e_reverse[to] = &e[en];
	en++;
}

//DFS
void Graph::DFS( int k ) {
	sign[k] = count;
	for( Edge *p = e_begin[k]; p; p=p->next )
		if( sign[p->to] != count )
			DFS( p->to );
	st[ sn++ ] = k;
}

//DFS2
void Graph::RDFS( int k ) {
	flag[k] = count;

	//把 顶点k 的边表加入到 强连通分量count 的边表中
	if( reduce && e_begin[k] ) {
		e_end[k]->next = e_reduced[count];
		e_reduced[count] = e_begin[k];
	}

	for( Edge *p = e_reverse[k]; p; p=p->next )
		if( flag[p->to] == -1 )
			RDFS( p->to );
}

int Graph::Strongly_Connected_Component( int n, bool reduce/* = false */) {
	int i, m;
	this->n = n;
	this->reduce = reduce;

	//DFS
	memset( sign, 0, sizeof sign );
	sn = 0;
	count = 1;

	for( i=0; i<n; i++ )
		if( sign[i] < count )
			DFS( i );
	
	//DFS again
	count = 0;
	memset( flag, -1, sizeof sign );

	if( reduce )
		memset( e_reduced, 0, sizeof e_reduced );//初始化新图边表

	
	while( sn-- ) { //按出栈顺序逆向DFS
		if( flag[st[sn]] == -1 ) {
			//新的强连通分量
			RDFS( st[sn] );
			count++;
		}
	}

	m = count;
	if( reduce )
		Reduced( count );//简化新图边表

	return m;
}

void Graph::Reduced( int m ) {
	int to;
	count = 2;

	for( int i=0; i<m; i++ ) {

		Edge *t = 0;

		for( Edge *q, *p = e_reduced[i]; p; p = q ) {
			q = p->next;
			to = flag[ p->to ];
			//if 不是指向自己 and 不是重边
			if( sign[to] < count ) {
				sign[to] = count;
				dis[to] = &p->dis;
				p->to = to;
				p->next = t;
				t = p;
			}
			else if( p->dis < *dis[to] )
				*dis[to] = p->dis;
		}

		e_reduced[i] = t;
		count ++; //count++ 避免清除sign
	}
}

Graph g;
int dis[500];
vector< pair<int,int> > e[500];

int dijstra( int s, int t, int n ) {
	int i, j, k, to, len;
	bool sign[500] = { 0 };
	Graph::Edge *p;

	for( i=0; i<n; i++ )
		dis[i] = 1000000000;

	dis[s] = 0;

	for( i=0; i<n; i++ ) {
		k = -1;
		for( j=0; j<n; j++ )
			if( !sign[j] && ( k < 0 || dis[j] < dis[k] ) )
				k = j;

		if( k < 0 || dis[k] == 1000000000 )
			return -1;

		if( k == t )
			return dis[k];

		sign[k] = true;
		
		for( p = g.e_reduced[k]; p; p=p->next ) {
			to = p->to;
			if( !sign[ to ] && (len=dis[k]+p->dis) < dis[ to ] )
				dis[ to ] = len;
		}
	}

	return -1;
}

int main( ) {
	int n, m, h;
	while( 1 ) {
		scanf( "%d%d", &n, &m );
		
		if( n == 0 && m == 0 )
			break;
		
		g.init( );

		while( m-- ) {
			int a, b, h;
			scanf( "%d%d%d", &a, &b, &h );
			g.insertEdge( a-1, b-1, h );
		}
		h = g.Strongly_Connected_Component( n, true );
		
		scanf( "%d", &m );

		while( m-- ) {
			int a, b, ans;
			scanf( "%d%d", &a, &b );
			ans = dijstra( g.flag[a-1], g.flag[b-1], h );
			if( ans >= 0 )
				printf( "%d\n", ans );
			else
				printf( "Nao e possivel entregar a carta\n" );
		}
		printf( "\n" );
	}
	return 0;
}