有没有老哥教教这个题怎么做

chengfu86 @ 2024-11-28 22:11:58

by Joe2011 @ 2024-11-28 22:20:09

@chengfu86 数据范围？

by chengfu86 @ 2024-11-28 22:26:15

@Joe2011 10^5。

by TeaQiLang @ 2024-11-28 22:40:20

选择一条入边，然后再选择一条出边，递归下一个点，直到所有点都处理完毕。如果最终选择的边数量与n相等，计数器加一。

by TeaQiLang @ 2024-11-28 22:44:52

#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int mxn = 100005;
vector<int> grh[mxn][2];
bool slt[mxn][2][2];
int dfs(int u,int n,int cnt) {
    if(u == n + 1){
        if(cnt == n){
            return 1;
        }
        return 0;
    }
    int ans = 0;
    for(int i = 0;i < 2;i++){
        if(!slt[u][0][i]) {
            slt[u][0][i] = true;
            for(int j = 0;j < 2;j++){
                if(!slt[u][1][j]){
                    slt[u][1][j] = true;
                    ans += dfs(u + 1,n,cnt + 1);
                    ans %= MOD;
                    slt[u][1][j] = false;
                }
            }
            slt[u][0][i] = false;
        }
    }
    return ans;
}
int main() {
    int n;
    cin>>n;
    for(int i = 1;i <= 2 * n;i++){
        int u,v;
        cin>>u;
        cin>>v;
        grh[u][0].push_back(v);
        grh[v][1].push_back(u);
    }
    memset(slt, false, sizeof(slt));
    cout<<dfs(1, n, 0);
    return 0;
}

by TeaQiLang @ 2024-11-28 22:48:55

@chengfu86

by chengfu86 @ 2024-11-28 22:49:07

@TeaQiLang你复杂度对吗，你这个不是 O(2^n) 的吗