Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用SPFA做的代码,不过用了600毫秒,很慢,希望高手指点一下

Posted by jibee at 2009-07-30 23:02:58 on Problem 2983
#include <iostream>
using namespace std;

const int MAXVERTEX = 1000;
const int MAXEDGE = 100000;

struct Edge{
	Edge* next;
	int vertex;
	int length;
};

class Queue{
public:
	Queue()
		:size(MAXVERTEX + 1)
	{}
	void init(){
		rear = 0;
		front = 0;
	}
	bool enqueue( int v ){
		if( (rear + 1)%size != front ){
			queue[rear] = v;
			rear = (rear + 1 )%size;
			return true;
		}
		return false;
	}
	
	bool dequeue( int& v ){
		if( rear != front ){
			v = queue[front];
			front = ( front + 1 )%size;
			return true;
		}
		return false;
	}
private:
	const int size;
	int queue[MAXVERTEX+1];
	int rear;
	int front;
};

struct Distance{
     int length;
	 int count;
};


// return true if modified, false if not modified 
bool relax( const int v, const Edge* e, Distance dist[] ){
	if( dist[v].length + e->length < dist[e->vertex].length ){
		dist[e->vertex].length = dist[v].length + e->length;
		return true;
	}
	return false;
}

// return true if has no negative circles
// false if has
bool spfa( int n, Queue& q, Edge* edge[], Distance dist[], bool isInQueue[] ){
    memset( dist, 0, sizeof( Distance ) * (n+1) );
	q.init();

	for( int k = 1; k <= n; k ++ ){
			q.enqueue( k );
			isInQueue[k] = true;
	}

	int curVertex;
	n -= 2;
	while( q.dequeue( curVertex ) ){
		isInQueue[curVertex] = false;
		for( const Edge* temp = edge[curVertex]; temp != NULL; temp = temp->next ){
			if( relax( curVertex, temp, dist ) ){
				if( !isInQueue[temp->vertex] ){
					if( dist[temp->vertex].count > n )
						return false;
					isInQueue[temp->vertex] = true;
				    q.enqueue( temp->vertex );
					dist[temp->vertex].count++;
					
				}
			}
		}
	}
	return true;
}

int main(){
	Edge* edgeStore = new Edge[MAXEDGE*2];
	Edge** edge = new Edge*[MAXVERTEX+1];
    Distance* dist = new Distance[MAXVERTEX+1];
	bool isInQueue[MAXVERTEX +1];
	Queue q;
	int n, m;
	while ( scanf( "%d%d%*c", &n, &m ) != EOF ){
		memset( edge, 0, sizeof( Edge* ) * (n +1) );
		int top = 0;
		for( int j = 0; j < m; j ++ ){
			char ch;
			scanf( "%c", &ch );
			if( ch == 'P' ){
					int a, b, d;
					scanf( "%d%d%d%*c", &a, &b, &d );
					Edge* curPtr = edgeStore + top++;
					curPtr ->vertex = b;
					curPtr ->length = -d;
					curPtr ->next = edge[a];
					edge[a] = curPtr;
					Edge* curPtr2 = edgeStore + top++;
					curPtr2 ->vertex = a;
					curPtr2 ->length = d;
					curPtr2 ->next = edge[b];
					edge[b] = curPtr2;
			}
			else{
					int a, b;
					scanf( "%d%d%*c", &a, &b );
					Edge* curPtr = edgeStore + top++;
					curPtr ->vertex = b;
					curPtr ->length = -1;
					curPtr ->next = edge[a];
					edge[a] = curPtr;
			}

		}

		if( spfa( n, q, edge, dist, isInQueue ) )
			printf( "Reliable\n" );
		else printf( "Unreliable\n" );
	}
    delete[] dist;
  delete[] edgeStore;
  delete[] edge;
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator