這題頗有挑戰性,給有向圖(directed graph),要找出圖上是否有環(cycle),也要找出所有點之間存在的所有路徑數量,當路徑經過環(即代表路徑數量無窮大),路徑數量要輸出-1。
我的作法是先以dp(Floyd-Warshall做變化)找出所有點之間存在的所有路徑數量,接著判斷是否有k->k (k = 1….n)路徑存在,若存在即為環存在,再跑一次迴圈將所有可與k相連的路徑的值設為-1。
在寫的時候原本Floyd-Warshall的觀念還是沒想清楚,在最外面多加了一層算「經過幾個點」的迴圈,寫出來超冗長且bug連連。後來改用recursive去產出所有組合,想當然Time Limit Exceed。苦思良久才領悟到不必多加那一層迴圈,也搞清楚找到環以後如何去刪掉所有受影響的節點了。柳暗花明,最後看到了清爽的程式碼 :))
不過仍然是跑了兩次三層迴圈,應該算O(2 * n^3)吧,一定可以更省,就繼續研究吧。
CODE
#include <iostream> using namespace std; #define MAX 30 int main(){ int i, j, k; int maxn, side, d1, d2, total; int matrix[MAX][MAX]; //total number of paths total = 0; while( cin >> side ){ for(i=0; i<MAX; i++) for(j=0; j<MAX; j++) matrix[i][j] = 0; maxn = -1; for(i=0; i<side; i++){ cin >> d1 >> d2; matrix[d1][d2] = 1; if( d1 > maxn ) maxn = d1; if( d2 > maxn ) maxn = d2; } maxn++; //findout all paths for(k=0; k<maxn; k++) for(i=0; i<maxn; i++) for(j=0; j<maxn; j++) if( matrix[i][k] * matrix[k][j] > 0 ) matrix[i][j] += matrix[i][k]; //eliminate paths involved cycles for(k=0; k<maxn; k++) if( matrix[k][k] != 0 ) //cycle for(i=0; i<maxn; i++) for(j=0; j<maxn; j++) if( matrix[i][k] * matrix[k][j] != 0 ) matrix[i][j] = -1; //output cout << "matrix for city " << total << endl; for(i=0; i<maxn; i++){ cout << matrix[i][0]; for(j=1; j<maxn; j++) cout << ' ' << matrix[i][j]; cout << endl; } total++; }//while return 0; }
No comments:
Post a Comment