SDNUOJ 1134 Facebook Floyd闭包传递计数

Description

据说任意两个人之间最多只需要借助六个人就可以认识对方, 现在给你n个好友的关系，问你这其中每个人之间最多借助几个人就能认识对方？

题目链接 ： http://www.acmicpc.sdnu.edu.cn/problem/show/1134

Floyd闭包传递

需要计数时，将bool型数组改为int，条件转移时对应题目改一下，相乘还是相加

Floyd不能“剪枝”，必须完整地执行完

新找到的路可能比当前最短路长，也可能更短，取二者min

Code

#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, m;
int beat[205][205];
map<string, int> mp;

void floyd()
{
    for(int k = 1; k <= n; ++k)
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(beat[i][k] && beat[k][j])
                    if(beat[i][j] == 0)
                        beat[i][j] = beat[j][i] = beat[i][k] + beat[k][j];
                    else
                        beat[i][j] = beat[j][i] = min(beat[i][j], beat[i][k] + beat[k][j]);
}

int main()
{
    scanf("%d%d", &n, &m);
    int cnt = 1;
    string c, d;
    memset(beat, 0, sizeof(beat));
    for(int i = 0; i < m; ++i)
    {
        cin >> c >> d;
        if(!mp[c])
            mp[c] = cnt++;
        if(!mp[d])
            mp[d] = cnt++;
        beat[ mp[c] ][ mp[d] ] = beat[ mp[d] ][ mp[c] ] = 1;
    }
    floyd();
    bool flag = 1;
    int ans = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
        {
            if(beat[i][j] == 0 && beat[j][i] == 0)
            {
                flag = 0;
                break;
            }
            else if(beat[i][j] > ans)
                ans = beat[i][j];
        }
    if(flag)
        cout << ans - 1 << '\n';
    else
        cout << "No" << '\n';
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

用1表示两人原本就认识，最终答案减一即可。如果用0，0 + 0永远是0。