题目描述
抽象题意:
给你一堆两两字母的关系,让你判断是否能推出所有字母的关系。
思路
• 确定两两各字母间的关系:
运用”A>B且B>C,则A>C“这个结论推各字母间的关系。
因此如果dist[A][B]==1 && dist[B][C]==1那么我们就可以让dist[A][C]=1。
(注:dist[i][j]=1表示能够确定i<j。而如果dist=0表示不能确定)
于是上面确定各字母的关系可以通过floyd算法来实现。
• 判定能否确定所有字母间的关系:
1.如果dist[i][i]=0:说明矛盾
2.如果dist[i][j]=0&&dist[j][i]=0:说明还无法确定i与j的关系
3.如果dist[i][j]或dist[j][i]必有一个=1:说明能确定i与j的关系
• 输出字母间的关系:
依次循环每个字母,如果对于这个字母来说dist[这个字母][枚举其他所有字母]都为1,
说明这个字母是最小的,输出。
算法1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static int N=36;
public static boolean[][] g=new boolean[N][N];
public static boolean[][] dist=new boolean[N][N];
public static boolean[] st=new boolean[N];
public static int n,m;
public static int type,count;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
while(true){
String[] s = br.readLine().split(" ");
n=Integer.parseInt(s[0]);
m=Integer.parseInt(s[1]);
if(n==0 && m==0){
break;
}
for(int i=0;i<n;i++){
Arrays.fill(g[i],false);
}
type=0;
count=0;
for(int i=1;i<=m;i++){
String s1 = br.readLine();
int a=s1.charAt(0)-'A';
int c=s1.charAt(2)-'A';
if(type==0){//如果还是不确定的话,继续循环
g[a][c]=true;
floyd();
type=check();
if(type!=0){ //0: 不确定 1:唯一确定 2:矛盾
count=i;//记录循环次数
}
}
}
if(type==0){
System.out.println("Sorted sequence cannot be determined.");
}else if(type==2){
System.out.println("Inconsistency found after "+count+" relations.");
}else {
Arrays.fill(st,false);
System.out.print("Sorted sequence determined after "+count+" relations: ");
for(int i=0;i<n;i++){
System.out.print(get_min());
}
System.out.println(".");
}
}
}
public static char get_min(){
for(int i=0;i<n;i++){
if(!st[i]){
int flag=0;
for(int j=0;j<n;j++){
if(i!=j && !st[j]&& dist[j][i]){ //j<i 说明i不是我们要找的最小值
flag=1;
break;
}
}
if(flag==0){//说明i就是我们要找的最小值
st[i]=true;
return (char)(i+'A');
}
}
}
return 'A';
}
public static int check(){
for(int i=0;i<n;i++){
if(dist[i][i]){
return 2;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(!dist[i][j] && !dist[j][i]){
return 0;
}
}
}
return 1;
}
public static void floyd(){
dist=g.clone();
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(dist[i][k] && dist[k][j]){
dist[i][j]=true;
}
}
}
}
}
}