就是一个差分约束系统

floyed实现

挺水的,求康康

#include<bits/stdc++.h>
using namespace std;
char s[60];
int minn[60][60],maxx[60][60];
int main( ){
	int n,A,B,i,j;
	cin>>n>>A>>B;
	for(i=1;i<=n;i++){
		cin>>(s+1);
		for(j=1;j<=n;j++)
		if(s[j]=='+'){
			minn[i][j]=1;
			maxx[i][j]=2;
		}else if(s[j]=='-'){
			minn[i][j]=-2;
			maxx[i][j]=-1;
		}else if(s[j]=='=')minn[i][j]=maxx[i][j]=0;
		else{
			minn[i][j]=-2;
			maxx[i][j]=2;
		}
		minn[i][i]=maxx[i][i]=0;
	}
	int k;
	for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	minn[i][j]=max(minn[i][j],minn[i][k]+minn[k][j]),maxx[i][j]=min(maxx[i][j],maxx[i][k]+maxx[k][j]);
	int c1=0,c2=0,c3=0;
	for(i=1;i<=n;i++){
		if(i==A||i==B)continue; 
		for(j=1;j<i;j++){
			if(j==A||j==B)continue;
			if(minn[i][A]>maxx[j][B]||minn[i][B]>maxx[j][A])c1++;
			if(minn[A][i]>maxx[B][j]||minn[B][i]>maxx[A][j])c3++;
			if((minn[A][i]==maxx[A][i]&&minn[B][j]==maxx[B][j]&&minn[A][i]==minn[B][j])
			||
			(minn[A][j]==maxx[A][j]&&minn[B][i]==maxx[B][i]&&minn[B][i]==minn[A][j]))c2++;
		}
	}
	cout<<c1<<" "<<c2<<" "<<c3<<endl;
}