思路

数据只有100，f[i][j]=代表i对j的赞同度，因为具有传递性那么有第三个人k，f[i][j]=max(f[i][j],min(f[i][k],f[k][j])),利用floyd算法传递即可即可$\\$ Floyd算法是一种用于计算图中所有节点对之间最短路径的动态规划算法，时间复杂度为O(n³)。它通过逐步更新每个节点间的距离，找到所有可能的中转节点来优化路径长度

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define N 105
#define int long long
int f[N][N];
int n, m, q;
signed main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		f[u][v] += 1;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
					f[i][j] = max(f[i][j], min(f[i][k], f[k][j]));
			}
		}
	}
	while (q--) {
		int u, v;
		cin >> u >> v;
		cout << f[u][v] << '\n';
	}
	return 0;
}

python

def main():
    N = 105
    f = [[0] * N for _ in range(N)]
    
    n, m, q = map(int, input().split())
    
    for _ in range(m):
        u, v = map(int, input().split())
        f[u][v] += 1
    
    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                f[i][j] = max(f[i][j], min(f[i][k], f[k][j]))
    
    for _ in range(q):
        u, v = map(int, input().split())
        print(f[u][v])

if __name__ == "__main__":
    main()

java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static final int N = 105;
    static long[][] f = new long[N][N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            f[u][v] += 1;
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    f[i][j] = Math.max(f[i][j], Math.min(f[i][k], f[k][j]));
                }
            }
        }

        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            System.out.println(f[u][v]);
        }
    }
}

题目内容

现在发的动态都有点赞功能。

如果A发的动态。B点赞了$x$次。那么B对A的赞同度为$x$，记为$f(B,A)$,并且$f(B,A)$和$f(A,B)$不一定相等。

并且赞同度具有传递性。$f(A,B)=max(f(A,B),min(f(A,C),f(C,B)))$,可以多次传递。

现在有几个人，他们之间有$m$条点赞记录。

现在有$Q$次询问，每次询问输入$u,v$(空格隔开)，询问$f(u,v)$的值。

输入描述

第一行输入三个整数$n,m,Q(1≤ n ≤100,1≤ m ≤ 10^5 ,1≤ Q ≤ 10^3)$

接下来$m$行，每行输入$u,v$(代表$u$给$v$点了一次赞,$1≤u,v≤n$)

接下来$Q$行，每行输入$u,v(1≤u,v≤n)$。

输出描述

对于每一个询问输出一个整数表示答案。

样例1

输入

2 7 4
1 1
1 2
1 2
2 1
2 1
2 1
2 2
1 1
1 2
2 1
2 2

输出

2
2
3
2