XOJ:http://acm.xmu.edu.cn/problem.php?id=1078

Description

　　人肉搜索與刺青、美白、護膚、減肥等直接在人肉上施行的種種行為無關。顧名思義，人肉搜索就是利用現代信息科技，變傳統的網絡信息搜索為人找人，人問人，人碰人，人擠人、人挨人的關系型網絡社區活動，變枯燥乏味的查詢過程為一人提問、八方回應，一石激起千層浪，一聲呼喚驚醒萬顆真心的人性化搜索體驗。人肉搜索不僅可以在最短時間內揭露某某門背后的真相，為某三某七找到大眾認可的道德定位，還可以在網絡無法觸及的地方，探尋并發現最美麗的叢林少女，最感人的高山牧民，最神秘的荒漠洞窟，最浪漫的終極邂逅…… 人肉搜索追求的最高目標是：不求最好，但求最肉。

－－谷歌四月一日的愚人節笑話

　　人肉搜索之所以強大，其原因在于世界上任何兩個人，要么他們是朋友，要么他們是朋友的朋友，要么他們是朋友的朋友的朋友，要么他們是朋友的朋友的朋友的朋友，要么他們是朋友的朋友的朋友的朋友的朋友。。。人肉搜索引擎正是利用了這一點，對于每個問題，人肉搜索開始M層的搜索，第一層是搜索我的朋友，第二層是搜索我朋友的朋友，第三層是使搜索我朋友的朋友的朋友。。。給一個人際關系表，問M至少要為多少才能保證所有人之間可以通過人肉搜索引擎搜索到。

Input

　　輸入的第一行包含一個正整數N(2 <= N <= 100)，表示總的人數。
　　輸入的第二行到第N+1行每行有N個整數，第i行第j列的數字Fij如果為1表示第i個人和第j個人是朋友，否則不是。保證F_ij?= F_ji，F_ii?= 1。

Output

　　輸出這N個人中，保證人肉搜索引擎的正常工作（即所有人都能被搜索到）前提下，M的最小值。如果存在兩個人他們不是朋友的朋友的朋友的。。。的朋友，則輸出-1。

Sample Input

4
1 0 1 1
0 1 0 1
1 0 1 0
1 1 0 1

Sample Output

2

Hint

樣例中，1和3是朋友，1和4是朋友，2和4是朋友。此時2和3之間間隔了1、4兩個人的關系，所以結果為2。

#include<stdio.h> #define MAX 10002 int isUnion[100]; int w[100][100]; int d[100], path[100]; void shortestPath(int p[][100], int n, int d[], int path[], int s) {for (int i = 0; i<n; ++i)if (p[s][i] != MAX)break;else if (i == n)return;for (int i = 0; i<n; ++i){d[i] = MAX;path[i] = -1;isUnion[i] = 0;}for (int i = 0; i<n; ++i){if (p[s][i] != MAX){d[i] = p[s][i];path[i] = s;}}isUnion[s] = 1;d[s] = 0;int min, t = s;for (int i = 1; i<n; ++i){min = MAX;for (int j = 0; j<n; ++j){if (isUnion[j] == 0 && d[j] < min){min = d[j];t = j;}}isUnion[t] = 1;for (int k = 0; k<n; ++k){if (p[t][k] != MAX)if (!isUnion[k] && d[k] > d[t] + p[t][k]){d[k] = d[t] + p[t][k];path[k] = t;}}} } int main() {int s, i, j, temp;FILE *file = freopen("in6.txt", "r", stdin);if (!file)return 1;scanf("%d", &s);if (s == 1){ printf("%d\n", 0); return 0; }for (i = 0; i<s; i++)for (j = 0; j<s; j++){scanf("%d", &temp);if (temp == 0)w[i][j] = MAX;else w[i][j] = temp;}temp = 0;for (j = 0; j<s; j++){shortestPath(w, s, d, path, j);for (i = 1; i<s; i++)if (d[i]>temp&&d[i] != MAX)temp = d[i];else if (d[i] == MAX){ printf("%d\n", -1); return 0; }}printf("%d\n", --temp);return 0; }

總結

以上是生活随笔為你收集整理的图算法--人肉搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。