偏序关系
Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description
给定有限集上二元关系的关系矩阵,确定这个关系是否是偏序关系。

Input
多组测试数据,对于每组测试数据,第1行输入正整数n(1 <= n <= 100),第2行至第n+1行输入n行n列的关系矩阵。

Output
对于每组测试数据,若为偏序关系,则输出yes,反之,则输出no。

Sample Input
4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
4
1 0 0 1
0 1 0 0
0 0 1 0
1 0 0 1
Sample Output
yes
no
Hint
偏序关系形式定义:设R是集合A上的一个二元关系,若R满足自反性、反对称性、传递性,则称R为A上的偏序关系。

思路:
满足:自反 反对称 传递就是偏序关系了
自反:矩阵主对角线全为1
反对称:矩阵除了对角线,a[i][j]为1则a[j][i]一定为0 a[i][j]为0对a[j][i]不作要求
传递:A²矩阵中a[i][j]为1如果A也为1则满足传递关系
直接贴代码了(c++):

#include<bits/stdc++.h>
using namespace std;

int b[105][105];
int graph[105][105];
int main()
{
	int n;
	while(cin>>n)
	{       memset(b,0,sizeof(b));   
		bool myself=true;
		bool consymmetry=true;
		bool transmit=true;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				cin>>graph[i][j];
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i==j)
				{
					if(graph[i][j]!=1)
					myself=false;	
				}
				if(i!=j)
				{
					if(graph[i][j]==1)
                                            if(graph[j][i]!=0)
						consymmetry=false;
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				for(int k=1;k<=n;k++)
				{
					b[i][j]+=(graph[i][k]*graph[k][j]);
				}
			}
		}
                /*for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
			         cout<<b[i][j]<<" ";
			}
                                  cout<<endl;
		} */
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(b[i][j]==1)
				{
					if(graph[i][j]!=1)
						transmit=false;
				}
			}
		}
		//cout<<"zifan:"<<myself<<"  fanduichen:"<<consymmetry<<"  transmit:"<<transmit<<endl;
		if(transmit&&consymmetry&&myself)
		{
			cout<<"yes"<<endl;
		}else
		{
			cout<<"no"<<endl;
		}
	}
}