题解 P2474 【[SCOI2008]天平】

### Preface 差分约束进阶题，有助于加深印象，也避免了对模板的固化。 刚开始写了 SPFA 后来发现不如 Floyd 方便就重构代码了…… ### Solution 题目有 $3$ 个问题，不妨先对 $A+B>C+D$ 进行思考。 原不等式等价于 $A-C>D-B$ 或 $A-D>C-B$。显然，数据量允许我们暴力枚举 $C,D$ 判断是否成立。 传统的差分约束是直接求出一组解。但这里直接的搭配的解不唯一很不方便，我们尝试维护变量间的和差关系以直接满足不等关系。 此时，我们就可以设 $f(u,v)$ 为 $u,v$ 的 $\max\{u-v\}$，$g(u,v)=\min\{u-v\}$。$u-v\le f(u,v)$ 或 $u-v\ge g(u,v)$ 相当于从 $v$ 出发到 $u$ 的最短/长路。而暴力枚举 $C,D$ 就要求我们跑全源最短路。 即，跑两次 Floyd，一次跑最短路得到 $f(u,v)$，一次跑最长路得到 $g(u,v)$。 ---------- 用邻接矩阵建图的时候， - 对于`+`，$i>j$，即 $i-j>0$，可以得到 $i-j=1$ 或 $i-j=2$，于是就有 $f(i,j)=2,g(i,j)=1$。 - 对于`-`，有 $i-j=-1$ 或 $i-j=-2$，即 $f(i,j)=-1,g(i,j)=-2$。 - 对于`=`，有 $i=j$，即 $f(i,j)=g(i,j)=0$。 - 对于`?`，$i,j$ 关系未知，就假设两种最极端的情况，把 $f(i,j)=2,g(i,j)=-2$。 ---------- 接下来就是如何判断不等关系成立。 对于 $A-C>D-B$，显然为了使结果唯一，必须使得 $g(A,C)>f(D,B)$，即前者的最小值都已经比后者的最大值还要大，那么结果肯定是唯一的左边大于右边。 同理，对于 $A-D>C-B$，就要使得 $g(A,D)>f(D,B)$。两个条件显然只要满足一个即可，用逻辑或连接。 将上述做法推广到 $3$ 个问题即可。 - 对于 $A+B=C+D$，等价于 $A-D=C-B$ 或 $A-C=D-B$，即 $f(A,D)=g(C,B)=g(A,D)=f(C,B)$ 或 $f(A,C)=g(D,B)=g(A,C)=f(D,B)$。 - 对于 $A+B<C+D$，等价于 $A-C<D-B$ 或 $A-D<C-B$，即 $f(A,C)<g(D,B)$ 或 $f(A,D)<g(C,B)$。 时间复杂度 $O(n^3)$。 ### Notice 由于我们要对多个问进行统计答案，于是可以写个函数来多次调用，传参的时候给一个 lambda 表达式来当作比较函数即可。可以减少码量并方便调试。**需要C++11。** 其余的只是代码繁琐而已，细心就行。 ### Code ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; typedef const int cint; cint MAXN=55; int n,A,B; int minn[MAXN][MAXN],maxx[MAXN][MAXN]; template<typename Comp> void floyd(int dis[MAXN][MAXN],const Comp func) { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=k && k!=j && i!=j) dis[i][j]=func(dis[i][j],dis[i][k]+dis[k][j]); } template<typename Comp> void solve(const Comp cmp) { int ans=0; for(int i=1;i<=n;i++) if(i!=A && i!=B) for(int j=i+1;j<=n;j++) if(j!=A && j!=B) if(cmp(A,B,i,j)) ans++; cout<<ans<<' '; } int main() { ios::sync_with_stdio(false); cin>>n>>A>>B; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { char ch;cin>>ch; if(ch=='+') { maxx[i][j]=2; minn[i][j]=1; } if(ch=='-') { maxx[i][j]=-1; minn[i][j]=-2; } if(ch=='?') { maxx[i][j]=2; minn[i][j]=-2; } } floyd(maxx,[&](cint a,cint b){return a<b?a:b;}); floyd(minn,[&](cint a,cint b){return a>b?a:b;}); solve([&](cint a,cint b,cint c,cint d) { return minn[a][c]>maxx[d][b] || minn[a][d]>maxx[c][b]; }); solve([&](cint a,cint b,cint c,cint d) { return (minn[a][c]==maxx[d][b] && maxx[a][c]==minn[d][b] && minn[d][b]==maxx[d][b]) || (minn[a][d]==maxx[c][b] && maxx[a][d]==minn[c][b] && minn[c][b]==maxx[c][b]); }); solve([&](cint a,cint b,cint c,cint d) { return maxx[a][c]<minn[d][b] || maxx[a][d]<minn[c][b]; }); cout<<endl; return 0; } ```