【BZOJ1077】天平（差分约束）

题面

BZOJ

洛谷

题解

利用矩阵可以很容易得到两个点之间的最大差和最小差，再利用这个信息判断即可。差分约束用\(Floyd\)计算。时间复杂度\(O(n^3)\)。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAX 55

int dmn[MAX][MAX],dmx[MAX][MAX];

int n,A,B,c1,c2,c3;

char ch[MAX];

int main()

{

	scanf("%d%d%d",&n,&A,&B);

	for(int i=1;i<=n;++i)

	{

		scanf("%s",ch+1);

		for(int j=1;j<=n;++j)

		{

			if(ch[j]=='='||i==j)dmn[i][j]=dmx[i][j]=0;

			else if(ch[j]=='+')dmn[i][j]=1,dmx[i][j]=2;

			else if(ch[j]=='-')dmn[i][j]=-2,dmx[i][j]=-1;

			else dmn[i][j]=-2,dmx[i][j]=2;

		}

	}

	for(int k=1;k<=n;++k)

		for(int i=1;i<=n;++i)

			for(int j=1;j<=n;++j)

			{

				if(i==j||j==k||k==i)continue;

				dmn[i][j]=max(dmn[i][j],dmn[i][k]+dmn[k][j]);

				dmx[i][j]=min(dmx[i][j],dmx[i][k]+dmx[k][j]);

			}

	for(int i=1;i<=n;++i)

		if(i!=A&&i!=B)

			for(int j=1;j<i;++j)

			{

				if(j==A||j==B)continue;

				if(dmn[A][i]>dmx[j][B]||dmn[B][i]>dmx[j][A])++c1;

				if(dmn[i][A]>dmx[B][j]||dmn[i][B]>dmx[A][j])++c3;

				if(dmn[A][i]==dmx[A][i]&&dmn[j][B]==dmx[j][B]&&dmn[A][i]==dmn[j][B])++c2;

				else if(dmn[B][i]==dmx[B][i]&&dmn[j][A]==dmx[j][A]&&dmn[B][i]==dmn[j][A])++c2;

			}

	printf("%d %d %d\n",c1,c2,c3);

	return 0;

}