QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671182#900. 一般图最大权匹配QingyyxWA 0ms7864kbC++205.1kb2024-10-24 11:31:162024-10-24 11:31:17

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 11:31:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7864kb
  • [2024-10-24 11:31:16]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define enl putchar('\n')
#define all(x) (x).begin(),(x).end()
#define debug(x) printf(" "#x":%d\n",x);
using namespace std;
const int MAXN = 500 + 5, MAXM = 500 * 500 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
typedef pair<int, int> pii;
char buf[1 << 21], * p1 = buf, * p2 = buf, obuf[1 << 21], * o = obuf, of[35];
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1)res = res * a % mod; n >>= 1; a = a * a % mod; }return res; }
template <class T = int>inline T read() { T s = 0, f = 1; char c = gc(); for (; !isdigit(c); c = gc())if (c == '-')f = -1; for (; isdigit(c); c = gc())s = s * 10 + c - '0'; return s * f; }
inline void read(int* a, int n) { for (int i = 1; i <= n; ++i)a[i] = read(); }
inline int inal(char* s) { int n = 0; for (s[0] = gc(); !isalpha(s[0]); s[0] = gc()); for (; isalpha(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline int indi(char* s) { int n = 0; for (s[0] = gc(); !isdigit(s[0]); s[0] = gc()); for (; isdigit(s[n]); s[++n] = gc()); return s[n] = 0, n; }
inline void outd(auto* a, int n) { for (int i = 1; i <= n; ++i)printf("%d ", a[i]); enl; }
int A[MAXN][MAXN], B[MAXN][MAXN], t[MAXN][MAXN], id[MAXN];
// 高斯消元 O(n^3)
// 在传入 B 时表示计算逆矩阵, 传入 nullptr 则只需计算矩阵的秩
void Gauss(int A[][MAXN], int B[][MAXN], int n) {
    if (B) {
        memset(B, 0, sizeof(t));
        for (int i = 1; i <= n; i++) B[i][i] = 1;
    }

    for (int i = 1; i <= n; i++) {
        if (!A[i][i]) {
            for (int j = i + 1; j <= n; j++)
                if (A[j][i]) {
                    swap(id[i], id[j]);
                    for (int k = i; k <= n; k++) swap(A[i][k], A[j][k]);

                    if (B)
                        for (int k = 1; k <= n; k++) swap(B[i][k], B[j][k]);
                    break;
                }
            if (!A[i][i]) continue;
        }

        int inv = qpow(A[i][i], mod - 2);

        for (int j = 1; j <= n; j++)
            if (i != j && A[j][i]) {
                int t = (ll)A[j][i] * inv % mod;

                for (int k = i; k <= n; k++)
                    if (A[i][k]) A[j][k] = (A[j][k] - (ll)t * A[i][k]) % mod;

                if (B) {
                    for (int k = 1; k <= n; k++)
                        if (B[i][k]) B[j][k] = (B[j][k] - (ll)t * B[i][k]) % mod;
                }
            }
    }

    if (B)
        for (int i = 1; i <= n; i++) {
            int inv = qpow(A[i][i], mod - 2);

            for (int j = 1; j <= n; j++)
                if (B[i][j]) B[i][j] = (ll)B[i][j] * inv % mod;
        }
}
bool row_marked[MAXN] = {false}, col_marked[MAXN] = {false};
int sub_n;  // 极大满秩子矩阵的大小

// 消去一行一列 O(n^2)
void eliminate(int r, int c) {
    row_marked[r] = col_marked[c] = true;  // 已经被消掉

    int inv = qpow(B[r][c], mod - 2);

    for (int i = 1; i <= sub_n; i++)
        if (!row_marked[i] && B[i][c]) {
            int t = (ll)B[i][c] * inv % mod;

            for (int j = 1; j <= sub_n; j++)
                if (!col_marked[j] && B[r][j])
                    B[i][j] = (B[i][j] - (ll)t * B[r][j]) % mod;
        }
}

int vertices[MAXN], girl[MAXN];  // girl 是匹配点, 用来输出方案

signed main(signed argc, char const* argv[]) {
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("contrast.out", "w", stdout);
#endif
    auto rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());

    int n, m;
    scanf("%d%d", &n, &m);  // 点数和边数

    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y); ++x, ++y;
        A[x][y] = rng() % mod;
        A[y][x] = -A[x][y];  // Tutte 矩阵
    }

    for (int i = 1; i <= n; i++)
        id[i] = i;  // 输出方案用的,因为高斯消元的时候会交换列
    memcpy(t, A, sizeof(t));

    Gauss(A, nullptr, n);

    for (int i = 1; i <= n; i++)
        if (A[id[i]][id[i]]) vertices[++sub_n] = i;  // 找出一个极大满秩子矩阵

    for (int i = 1; i <= sub_n; i++)
        for (int j = 1; j <= sub_n; j++) A[i][j] = t[vertices[i]][vertices[j]];

    Gauss(A, B, sub_n);

    for (int i = 1; i <= sub_n; i++)
        if (!girl[vertices[i]])
            for (int j = i + 1; j <= sub_n; j++)
                if (!girl[vertices[j]] && t[vertices[i]][vertices[j]] && B[j][i]) {
                    // 注意上面那句 if 的写法, 现在 t 是邻接矩阵的备份,
                    // 逆矩阵 j 行 i 列不为 0 当且仅当这条边可行
                    girl[vertices[i]] = vertices[j];
                    girl[vertices[j]] = vertices[i];

                    eliminate(i, j);
                    eliminate(j, i);
                    break;
                }

    printf("%d\n", sub_n / 2);
    for (int i = 1; i <= n; i++)
        if (girl[i] && i < girl[i])printf("%d %d\n", girl[i] - 1, i - 1);
    enl;
    //=============================================================
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7864kb

input:

18 120
12 10 6
13 0 10
1 0 6
8 12 5
5 14 3
2 8 1
2 11 5
7 10 1
0 7 7
7 12 2
14 12 3
6 12 10
12 5 5
8 16 5
7 3 5
5 7 10
17 12 7
16 11 2
6 11 9
0 14 2
9 17 8
12 11 2
3 0 9
13 3 7
9 2 5
14 17 9
1 15 3
16 12 3
2 17 7
17 5 2
8 5 1
5 9 7
14 13 5
7 4 1
1 6 6
14 2 7
7 9 5
12 9 10
13 6 3
13 12 2
13 2 7
4 13 ...

output:

9
1 0
3 2
7 4
8 5
11 6
15 9
14 10
17 12
16 13


result:

wrong answer there isn't edge (9, 14)