qt!差分约束90pts!悬赏1关注
查看原帖
qt!差分约束90pts!悬赏1关注
748854
FunKingDoor楼主2022/9/16 21:32
#include <iostream>
using namespace std;

const int MX = 51;

int dis1[MX][MX], dis2[MX][MX], n, sa, sb;

void floyd(){
    for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++) {
				if(i == j || i == k || j == k) continue;
				dis2[i][j] = min(dis2[i][j], dis2[i][k] + dis2[k][j]);
				dis1[i][j] = max(dis1[i][j], dis1[i][k] + dis1[k][j]);
			}
		}
	}
}

int main(){
	cin >> n >> sa >> sb;
	for(int i = 1; i <= n; i++){
        string str;
        cin >> str;
		for(int j = 1; j <= n; j++) {
			char ch = str[j - 1];
            if(i == j) {
                dis1[i][j] = dis2[i][j] = 0;
                continue;
            }
			switch(ch){
				case '=':
					dis1[i][j] = dis2[i][j] = 0;
					break;
				case '+':
					dis1[i][j] = 1;
					dis2[i][j] = 2;
					break;
				case '-':
					dis1[i][j] = -2;
					dis2[i][j] = -1;
					break;
				default:
					dis1[i][j] = -2;
					dis2[i][j] = 2;
			}
		}
	}
    floyd();
	int c1 = 0, c2 = 0, c3 = 0;
	for(int i = 1; i <= n; i++){ 
        if(i == sa || i == sb) continue;
        for(int j = 1; j < i; j++){
            if(j == sa || j == sb) continue;
            if(dis1[sa][i] > dis2[j][sb] || dis1[sb][i] > dis2[j][sa]) c1++;
            if(dis1[sa][i] == dis2[sa][i] && dis1[j][sb] == dis2[j][sb] && dis1[sa][i] == dis1[j][sb]) c2++; 
            if(dis1[i][sa] > dis2[sb][j] || dis1[i][sb] > dis2[sa][j]) c3++;
        }
    }
    cout << c1 << ' ' << c2  << ' ' << c3;
	return 0;
}
2022/9/16 21:32
加载中...