原题地址本题就是,有N个变量,其取值只可能有三种:1、2、3。现在已知它们之间的一些大小关系,求有多少对变量(I, J)满足(I的值+J的值)一定>或=或<(A的值+B的值),A、B是指定的两个变量,且I、J、A、B互不相同。
首先,对于值相等的变量,直接建出无向图,按连通块缩点,再考虑大于/小于关系,如果I的值大于J则在I所在连通块与J所在连通块之间连一条有向边(从I到J)……这样,凡是既有前趋,又有后继的点(缩成的点,下同),其值只能是2,它的所有前趋的值只能是3,所有后继的值只能是1。除此以外,木有其它办法能唯一确定某个变量的值。
接下来最关键的一步——枚举I、J以及I、J、A、B的值,判断是否合法:
(1)如果某个变量的值已确定,且与枚举的值不同,不合法;
(2)如果某个变量有前趋,那么它的值就不能是3;如果有后继,那么它的值就不能是1;
(3)(这是最容易搞疵的)对于I、J、A、B之间已知的大小关系,要判断是否能全部满足,
注意这里的I、J、A、B是指缩成以后的点,而不是原来的变量(本沙茶一开始用原来的变量判断,结果WA了,后来把数据弄下来看了一下,是这里搞疵了囧……不过只跪了2个点,总共20个点),因为有可能它们本身之间木有给出关系,但那些与它在一个连通块中的(即与它值相等)的变量之间给出了关系。
至于枚举……由于本题数据小,只需要暴力枚举就行了囧……
本题的启示:考虑问题要周全,要设法考虑到所有情况。
代码:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 61, MAXM = 8000, INF = ~0U >> 2;
struct edge {
int a, b, pre, next;
} _E[MAXM + MAXM + MAXN], E[MAXM + MAXM + MAXN], E2[MAXM + MAXM + MAXN];
int n, _m, m, No1, No2;
int n0, A[MAXN][MAXN], A2[MAXN][MAXN], Q[MAXN], D[MAXN], W[MAXN], ST[MAXN][MAXN], res1 = 0, res2 = 0, res3 = 0;
bool vst[MAXN];
char ss[MAXN + 1];
void init_d0()
{
re(i, n) _E[i].pre = _E[i].next = i;
if (n & 1) _m = n + 1; else _m = n;
}
void init_d()
{
re(i, n0) E[i].pre = E[i].next = E2[i].pre = E2[i].next = i; m = n0;
}
void add_edge0(int a, int b)
{
_E[_m].a = a; _E[_m].b = b; _E[_m].pre = _E[a].pre; _E[_m].next = a; _E[a].pre = _m; _E[_E[_m].pre].next = _m++;
_E[_m].a = b; _E[_m].b = a; _E[_m].pre = _E[b].pre; _E[_m].next = b; _E[b].pre = _m; _E[_E[_m].pre].next = _m++;
}
void add_edge(int a, int b)
{
E[m].a = a; E[m].b = b; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m;
E2[m].a = b; E2[m].b = a; E2[m].pre = E2[b].pre; E2[m].next = b; E2[b].pre = m; E2[E2[m].pre].next = m++;
}
void init()
{
scanf("%d%d%d", &n, &No1, &No2); init_d0(); No1--; No2--;
re(i, n) {
scanf("%s", ss);
re(j, n) if (i != j) {
if (ss[j] == '?') A[i][j] = 0;
else if (ss[j] == '+') A[i][j] = 1;
else if (ss[j] == '-') A[i][j] = 2; else {A[i][j] = 3; add_edge0(i, j);}
}
}
}
void prepare()
{
re(i, n) re(j, n) if (i != j) {
if (A[i][j] == 1) A[j][i] = 2;
if (A[i][j] == 2) A[j][i] = 1;
if (A[i][j] == 3) A[j][i] = 3;
}
re(i, n) {W[i] = 0; vst[i] = 0;} int x, y; n0 = 0;
re(i, n) if (!vst[i]) {
vst[i] = 1; Q[0] = i; D[i] = n0;
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=_E[x].next; p != x; p=_E[p].next) {
y = _E[p].b;
if (!vst[y]) {vst[y] = 1; Q[++rear] = y; D[y] = n0;}
}
}
n0++;
}
init_d(); re(i, n0) re(j, n0) A2[i][j] = 0;
re(i, n) re(j, n) if (D[i] != D[j]) {
if (A[i][j] == 1) add_edge(D[i], D[j]); else if (A[i][j] == 2) add_edge(D[j], D[i]);
}
re(i, n) re(j, n) if (i != j && A[i][j]) A2[D[i]][D[j]] = A[i][j];
}
void solve()
{
int x; re(i, n) re(j, n) ST[i][j] = 0;
re(i, n0) if (E[i].next != i && E2[i].next != i) {
W[i] = 2;
for (int p=E[i].next; p != i; p=E[p].next) {
x = E[p].b; W[x] = 1;
}
for (int p=E2[i].next; p != i; p=E2[p].next) {
x = E2[p].b; W[x] = 3;
}
}
int d1 = D[No1], d2 = D[No2], di, dj;
re(i, n) re2(j, i+1, n) if (i != No1 && i != No2 && j != No1 && j != No2) {
di = D[i]; dj = D[j];
re1(si, 3) {re1(sj, 3) {re1(s1, 3) {re1(s2, 3) {
if (W[di] && si != W[di]) continue;
if (W[dj] && sj != W[dj]) continue;
if (W[d1] && s1 != W[d1]) continue;
if (W[d2] && s2 != W[d2]) continue;
if (E[di].next != di && si == 1) continue;
if (E2[di].next != di && si == 3) continue;
if (E[dj].next != dj && sj == 1) continue;
if (E2[dj].next != dj && sj == 3) continue;
if (E[d1].next != d1 && s1 == 1) continue;
if (E2[d1].next != d1 && s1 == 3) continue;
if (E[d2].next != d2 && s2 == 1) continue;
if (E2[d2].next != d2 && s2 == 3) continue;
if (A2[di][dj] == 1 && si <= sj) continue;
if (A2[di][dj] == 2 && si >= sj) continue;
if (A2[di][dj] == 3 && si != sj) continue;
if (A2[di][d1] == 1 && si <= s1) continue;
if (A2[di][d1] == 2 && si >= s1) continue;
if (A2[di][d1] == 3 && si != s1) continue;
if (A2[di][d2] == 1 && si <= s2) continue;
if (A2[di][d2] == 2 && si >= s2) continue;
if (A2[di][d2] == 3 && si != s2) continue;
if (A2[dj][d1] == 1 && sj <= s1) continue;
if (A2[dj][d1] == 2 && sj >= s1) continue;
if (A2[dj][d1] == 3 && sj != s1) continue;
if (A2[dj][d2] == 1 && sj <= s2) continue;
if (A2[dj][d2] == 2 && sj >= s2) continue;
if (A2[dj][d2] == 3 && sj != s2) continue;
if (A2[d1][d2] == 1 && s1 <= s2) continue;
if (A2[d1][d2] == 2 && s1 >= s2) continue;
if (A2[d1][d2] == 3 && s1 != s2) continue;
if (s1 + s2 > si + sj) x = 1;
else if (s1 + s2 == si + sj) x = 2; else x = 3;
if (!ST[i][j]) ST[i][j] = x; else if (ST[i][j] != x) {ST[i][j] = -1; break;}
} if (ST[i][j] == -1) break;} if (ST[i][j] == -1) break;} if (ST[i][j] == -1) break;}
}
re(i, n) re2(j, i+1, n) if (ST[i][j] == 1) res1++; else if (ST[i][j] == 2) res2++; else if (ST[i][j] == 3) res3++;
}
void pri()
{
printf("%d %d %d\n", res1, res2, res3);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}