HDU 5961傳遞 思維 + bitset

傳送門：HDU 5961

題意：中文題

思路：這題如果按hdu上的6s時限的話就有很多做法了，從每個點開始bfs判斷是否有長度大于等于2的最短路徑，或者dfs判斷給出的圖中是否有三元環等等，但是據說現場賽是1500ms時限，那這些做法就都不行了。

能在現場賽實作下通過的一個方法是用bitset将每個點的出邊儲存下來，然後枚舉每一條邊，判斷該邊的兩個端點的出邊是否都為下圖的情況

即判斷是否隻要有BC邊就有AC邊，具體做法就是用bitset[B] & bitset[A]看看結果是否等于bitset[B]

這樣複雜度就是O(n ^ 2 / 64)了。

盡管我已經盡我所能優化了代碼，但是還是很卡時間上限，多交幾次才能有一次卡進1500ms内。。

代碼：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2017;
const int MAXM = MAXN * MAXN;
struct node{
    int v, next;
    node(int _v = 0, int _next = 0) : v(_v), next(_next) {}
}mp[MAXM];
int pre[MAXN], cnt, n;
bitset<MAXN> g[MAXN];
void init()
{
    for(int i = 0; i < n; i++) g[i].reset();
    memset(pre, -1, sizeof(int) * n);
    cnt = 0;
}
void addedge(int u, int v)
{
    mp[cnt] = node(v, pre[u]); pre[u] = cnt++;
}
char s[MAXN][MAXN];
bool check(char ch)
{
    init();
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(s[i][j] == ch)
            addedge(i, j), g[i][j] = 1;
    for(int i = 0; i < n; i++)
        for(int j = pre[i]; ~j; j = mp[j].next)
        if((g[i] & g[mp[j].v]) != g[mp[j].v])
        return 0;
    return 1;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%s", s[i]);
        if(!check('P') || !check('Q')) puts("N");
        else puts("T");
    }
}