传递闭包

从关系图的角度来说，就是如果原关系图上有 i 到 j 的路径，则其传递闭包的关系图上就应有从 i 到 j 的边。通俗地讲，就是确定每个点是否能到达其他每个点。

把Floyd最短路算法稍微改一下即可。设E是原来的关系矩阵，则可以这样写：

修改得到

for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (E[i][k] && E[k][j])
                E[i][j] = 1;

E[i][j]如果等于1，则表示存在从i到j的路径。

【模板】传递闭包

题目描述

给定一张点数为 \(n\) 的有向图的邻接矩阵，图中不包含自环，求该有向图的传递闭包。

一张图的邻接矩阵定义为一个 \(n\times n\) 的矩阵 \(A=(a_{ij})_{n\times n}\)，其中

\[ a_{ij}=\left\{ \begin{aligned} 1,i\ 到\ j\ 存在直接连边\\ 0,i\ 到\ j\ 没有直接连边 \\ \end{aligned} \right. \] 一张图的传递闭包定义为一个 \(n\times n\) 的矩阵 \(B=(b_{ij})_{n\times n}\)，其中

\[ b_{ij}=\left\{ \begin{aligned} 1,i\ 可以直接或间接到达\ j\\ 0,i\ 无法直接或间接到达\ j\\ \end{aligned} \right. \]

输入格式

输入数据共 \(n+1\) 行。

第一行一个正整数 \(n\)。

第 \(2\) 到 \(n+1\) 行每行 \(n\) 个整数，第 \(i+1\) 行第 \(j\) 列的整数为 \(a_{ij}\)。

输出格式

输出数据共 \(n\) 行。

第 \(1\) 到 \(n\) 行每行 \(n\) 个整数，第 \(i\) 行第 \(j\) 列的整数为 \(b_{ij}\)。

样例 #1

样例输入 #1

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

样例输出 #1

1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1

提示

对于 \(100\%\) 的数据，\(1\le n\le 100\)，保证 \(a_{ij}\in\{0,1\}\) 且 \(a_{ii}=0\)。

#include<bits/stdc++.h>
using namespace std;
int d[110][110],n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>d[i][j];
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				d[i][j]=max(d[i][j],min(d[i][k],d[k][j]));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			cout<<d[i][j]<<" ";
		cout<<'\n';
	}
}

Description

There are N beads which of the same shape and size, but with different weights. N is an odd number and the beads are labeled as 1, 2, ..., N. Your task is to find the bead whose weight is median (the ((N+1)/2)th among all beads). The following comparison has been performed on some pairs of beads: A scale is given to compare the weights of beads. We can determine which one is heavier than the other between two beads. As the result, we now know that some beads are heavier than others. We are going to remove some beads which cannot have the medium weight.

For example, the following results show which bead is heavier after M comparisons where M=4 and N=5.

1.	Bead 2 is heavier than Bead 1.
2.	Bead 4 is heavier than Bead 3.
3.	Bead 5 is heavier than Bead 1.
4.	Bead 4 is heavier than Bead 2.

From the above results, though we cannot determine exactly which is the median bead, we know that Bead 1 and Bead 4 can never have the median weight: Beads 2, 4, 5 are heavier than Bead 1, and Beads 1, 2, 3 are lighter than Bead 4. Therefore, we can remove these two beads.

Write a program to count the number of beads which cannot have the median weight.

Input

The first line of the input file contains a single integer t (1 <= t <= 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows: The first line of input data contains an integer N (1 <= N <= 99) denoting the number of beads, and M denoting the number of pairs of beads compared. In each of the next M lines, two numbers are given where the first bead is heavier than the second bead.

Output

There should be one line per test case. Print the number of beads which can never have the medium weight.

Sample

Sample Input
1
5 4
2 1
4 3
5 1
4 2
Sample Output
2

题意：

　　有N个珠子，N为奇数，给出一些信息如a b表示a比b重，通过这些信息可以分析出那些珠子按重量排序后，哪个不可能是中间那个，求可以分析出几个。 如果a比b重，b比c重，则a比c重。

思路：

如果确定有（n+1)/2 多个比这个重，或者比这个轻，则表示这个珠子一定不是中间那个。计算出度和入度，如果出度大于（n+1)/2 或者 入度大于 （n+1)/2 ，则表示这个不是中间。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int map[110][110];
int n,m;
void floyd()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(map[i][k]==1&&map[k][j]==1)//传递
                    map[i][j]=1;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        memset(map,0,sizeof(map));
        for(int i=0; i<m; i++)
        {
            int a,b;
            cin>>a>>b;
            map[a][b]=1;
        }
        floyd();
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            int d=0,x=0;
            for(int j=1; j<=n; j++)
            {
                if(map[i][j])//计算出度
                    d++;
                else if(map[j][i])//计算入度
                    x++;
            }
            if(d>=(n+1)/2||x>=(n+1)/2)//出度或者入度其中有一个大于(n+1)/2就能证明不是中间
                ans++;
        }
        cout<<ans<<endl;
    }
}

[USACO08JAN] Cow Contest S

题目描述

$ N (1 ≤ N ≤ 100) $ cows, conveniently numbered $ 1 ~ N $ , are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow $ A $ has a greater skill level than cow $ B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) $, then cow $ A $ will always beat cow $ B $ .

Farmer John is trying to rank the cows by skill level. Given a list the results of $ M (1 ≤ M ≤ 4,500) $ two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

FJ的 \(N\)（\(1 \leq N \leq 100\)）头奶牛们最近参加了场程序设计竞赛。在赛场上，奶牛们按 \(1, 2, \cdots, N\) 依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为 \(A\) 的奶牛的编程能力强于编号为 \(B\) 的奶牛 （\(1 \leq A, B \leq N\)，\(A \neq B\))，那么她们的对决中，编号为 \(A\) 的奶牛总是能胜出。 FJ 想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 \(M\)（\(1 \leq M \leq 4,500\)）轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

输入格式

第一行两个用空格隔开的整数 \(N, M\)。

第 \(2\sim M + 1\) 行，每行为两个用空格隔开的整数 \(A, B\) ，描述了参加某一轮比赛的奶牛的编号，以及结果（每行的第一个数的奶牛为胜者）。

输出格式

输出一行一个整数，表示排名可以确定的奶牛的数目。

样例 #1

样例输入 #1

5 5
4 3
4 2
3 2
1 2
2 5

样例输出 #1

2

提示

样例解释：

编号为 \(2\) 的奶牛输给了编号为 \(1, 3, 4\) 的奶牛，也就是说她的水平比这 \(3\) 头奶牛都差。而编号为 \(5\) 的奶牛又输在了她的手下，也就是说，她的水平比编号为 \(5\) 的奶牛强一些。于是，编号为 \(2\) 的奶牛的排名必然为第 \(4\)，编号为 \(5\) 的奶牛的水平必然最差。其他 \(3\) 头奶牛的排名仍无法确定。

floyed算法

floyed不仅能求任意两点的最短路，还能求一个点能否到另一个点。

f[i][j]=f[i][j]|(f[i][k]&f[k][j])表示i能否走到j，即要么一开始i能到j,要么i能到k，k再能到j。

那么这里表示的是i能否赢j。用floyed求出每个点与个点的关系，只要这个点和其他

n-1个点的关系都确定了，就能确定他的排名。

#include<bits/stdc++.h>
using namespace std;
int a,b,n,m;
int f[101][101];
int ans;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		f[a][b]=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]=f[i][j]|f[i][k]&f[k][j];
			//表示是否连通
		}
	}
}
	
	for(int i=1;i<=n;i++)
	{
		int gg=1;
		for(int j=1;j<=n;j++)
		{
			if(i==j)
			continue;
			else{
				gg=gg&(f[i][j]|f[j][i]);
			}
		
		}
	ans+=gg;	
	}
	cout<<ans;
}