【AHOI2013复仇】SCOI2008 天平

Posted on 2012-09-25 21:26 Mato_No1 阅读(733) 评论(0)  编辑 收藏 引用 所属分类: 搜索SCOI
原题地址
本题就是,有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 + 1else _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] = 2else {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 == 1continue;
            
if (E2[di].next != di && si == 3continue;
            
if (E[dj].next != dj && sj == 1continue;
            
if (E2[dj].next != dj && sj == 3continue;
            
if (E[d1].next != d1 && s1 == 1continue;
            
if (E2[d1].next != d1 && s1 == 3continue;
            
if (E[d2].next != d2 && s2 == 1continue;
            
if (E2[d2].next != d2 && s2 == 3continue;
            
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 = 2else x = 3;
            
if (!ST[i][j]) ST[i][j] = x; else if (ST[i][j] != x) {ST[i][j] = -1break;}
        } 
if (ST[i][j] == -1break;} if (ST[i][j] == -1break;} if (ST[i][j] == -1break;}
    }
    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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理