Vertex Verse｜图上模拟与遍历

T5 - Vertex Verse

题目链接跳转：点击跳转

直接模拟情况就可以了，但是细节比较多需要注意一下。

时间复杂度

其中 work 函数会在每次迭代中被调用 $4$ 次，每次的复杂度是 $O(E)$。因此，对于每个输入的 $q$ 对点，总的时间复杂度是 $\Theta(4 \times q \times E)$，即$O(q \times E)$。但在最坏情况下，图中的边数 $E$ 可以接近 $O(n \times m)$，因此总时间复杂度是 $O(q \times n \times m)$​。

代码实现

本题的 C++ 代码如下：

#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

int n, m, q, ei;
int a, b, c, d;
int macw, alex;
struct perEdge{
    int to;
    int next;
} edges[2000005];
int vertex[1000005], cnt;
bool vis[1000005], memo[1000005][5], track;

inline int calc_dir(int x, int y){
    if (x + 1 == y) return 1;
    if (x + m == y) return 2;
    if (x + m + 1 == y) return 3;
    return -1;
}

void add(int v1, int v2){
    ei += 1;
    edges[ei].to = v2;
    edges[ei].next = vertex[v1];
    vertex[v1] = ei;
}

void dfs(int x, int steps, int origin, int dir){
    if (steps > 4) return ;
    if (steps == 4 && x == origin){
        // 说明走一圈可以走到原点。
        // 判断这个环是否已经被之前记录过了。
        if (memo[origin][dir]) return ;
        memo[origin][dir] = 1;
        cnt += 1;
        return ;
    }
    for (int index = vertex[x]; index; index = edges[index].next){
        int to = edges[index].to;
        // 只走编号比自己大的点。
        if (to >= origin || (to == origin && steps + 1 == 4)){
            if (vis[to]) continue;
            vis[to] = 1;
            dfs(to, steps + 1, origin, dir);
            vis[to] = 0;
        }
    }
}

void work(int x){
    for (int index = vertex[x]; index; index = edges[index].next){
        int to = edges[index].to;
        if (to <= x) continue;
        int dir = calc_dir(x, to);
        if (dir != -1){
            vis[to] = 1;
            dfs(to, 1, x, dir);
            vis[to] = 0;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for (int i=1; i<=2*q; i++){
        cin >> a >> b >> c >> d;
        int v1 = (a - 1) * m + b;
        int v2 = (c - 1) * m + d;
        add(v1, v2); add(v2, v1);
        // 从v1点开始走四步，看一下能否回到原点
        cnt = 0;
        if (a == c){ 
            // 在同一排
            work(v1); work(v2);
            work(v1 - m); work(v2 - m);
        } else if (b == d){
            // 在同一列
            work(v1); work(v2);
            work(v1 - 1); work(v2 - 1);
        }
        if (i % 2) macw += cnt / 2;
        else alex += cnt / 2;
    }
    cout << macw << " " << alex << endl;
    return 0;
}

另一种写法如下：

#include <iostream>
#include <unordered_map>
#include <map>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int N = 2e5 + 10;
map<pi,map<pi,int>> dis;
int mp[2];
bool check(pi a,pi b,pi c,pi d) {
    return dis[a][b] && dis[a][c] && dis[c][d] && dis[b][d];
}
int main() {
    int n,m,q;
    cin >> n >> m >> q;
    q <<= 1;
    for (int i=0;i<q;i++) {
        pi a,b;
        cin >> a.first >> a.second >> b.first >> b.second;
        if (a > b) swap(a,b);
        dis[a][b]++;
        if (dis[a][b] > 1) {
            continue;
        }
        if (a.first == b.first) {
            pi c = make_pair(a.first + 1,a.second);
            pi d = make_pair(b.first + 1,b.second);
            if (check(a,b,c,d)) {
                mp[i%2]++;
            }
            pi e = make_pair(a.first - 1,a.second);
            pi f = make_pair(b.first - 1,b.second);
            if (check(e,f,a,b)) {
                mp[i%2]++;
            }
        }else {
            pi c = make_pair(a.first,a.second + 1);
            pi d = make_pair(b.first,b.second + 1);
            if (check(a,c,b,d)) {
                mp[i%2]++;
            }
            pi e = make_pair(a.first,a.second - 1);
            pi f = make_pair(b.first,b.second - 1);
            if (check(e,a,f,b)) {
                mp[i%2]++;
            }
        }
    }
    cout << mp[0] << " " << mp[1] << endl;
    return 0;
}