先考虑如何求出任意两数的最大差值和最小差值,直接差分约束建图跑floyd求最短路和最长路即可
然后枚举i和j,考虑dA+dB和di+dj的关系,分两种情况移项,转化成dA-di和dj-dB的关系或dA-dj和di-dB的关系(只要有一个关系确定即确定)即可考虑(由于不等式都是两个变量,因此一定无法形成dA-dj和dB-di的固定关系)

 1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,x,y,c1,c2,c3,mx[105][105],mn[105][105];
4 char s[105];
5 int main(){
6 scanf("%d%d%d",&n,&x,&y);
7 x--;
8 y--;
9 for(int i=0;i<n;i++){
10 scanf("%s",s);
11 for(int j=0;j<n;j++){
12 mx[i][j]=2;
13 mn[i][j]=-2;
14 if (s[j]=='+')mn[i][j]=1;
15 if (s[j]=='-')mx[i][j]=-1;
16 if ((i==j)||(s[j]=='='))mx[i][j]=mn[i][j]=0;
17 }
18 }
19 for(int i=0;i<n;i++)
20 for(int j=0;j<n;j++)
21 for(int k=0;k<n;k++){
22 mn[j][k]=max(mn[j][k],mn[j][i]+mn[i][k]);
23 mx[j][k]=min(mx[j][k],mx[j][i]+mx[i][k]);
24 }
25 for(int i=0;i<n;i++)
26 for(int j=0;j<i;j++){
27 if ((i==x)||(i==y)||(j==x)||(j==y))continue;
28 if ((mn[x][i]>mx[j][y])||(mn[x][j]>mx[i][y]))c1++;
29 if ((mx[x][i]<mn[j][y])||(mx[x][j]<mn[i][y]))c3++;
30 if ((mx[x][i]==mn[x][i])&&(mx[j][y]==mn[j][y])&&(mx[x][i]==mx[j][y])||
31 (mx[x][j]==mn[x][j])&&(mx[i][y]==mn[i][y])&&(mx[x][j]==mx[i][y]))c2++;
32 }
33 printf("%d %d %d",c1,c2,c3);
34 }

最新文章

  1. 异步与并行~ReaderWriterLockSlim实现的共享锁和互斥锁
  2. 四则运算之C++实现篇
  3. 黑马程序员:Java编程_String
  4. go语言入门
  5. Installing scikit-learn
  6. 【转】 Linux/Unix 进程间通信的各种方式及其比较
  7. javascript实现的手风琴折叠菜单效果
  8. SQL基础--&gt;层次化查询(START BY ... CONNECT BY PRIOR)[转]
  9. c语言中的#ifndef、#def、#endif等宏是什么意思
  10. Bootstrap 响应式瀑布流 (使用wookmark)
  11. POJ1797 Heavy Transportation 【Dijkstra】
  12. [Codeforces 864F]Cities Excursions
  13. eclipse 设置maven来自动下载源码与doc
  14. git添加秘钥提示Key is already in use
  15. C++的一些小Tip
  16. 学习笔记——Ubuntu下使用Docker包部署禅道任务管理系统
  17. C++ 类2
  18. CI集成 mesos 资源分配的思考, 待续
  19. Asp.Net Core异常处理整理
  20. jdk和jre区别

热门文章

  1. iOS Swift结构体与类的方法调度
  2. 题解 [HNOI2019]序列
  3. OpenGL思维导图
  4. 2020BUAA软工个人博客作业-软件案例分析
  5. elasticsearch父子文档处理(join)
  6. 2021.10.9考试总结[NOIP模拟72]
  7. IPv6(诞生原因、数据报格式、与IPv4的不同、地址表现形式、基本地址类型、IPv6与IPv4的过渡策略)
  8. 洛谷 P5658 [CSP-S2019] 括号树
  9. Veritas Backup Exec™ 21.3 Multilingual (Windows)
  10. IDA*、操作打表、并行处理-The Rotation Game HDU - 1667