BZOJ3168. [HEOI2013]钙铁锌硒维生素(线性代数+二分图匹配)

Wesley13
• 阅读 390

##题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=3168

题解

首先,我们需要求出对于任意的 $i, j(1 \leq i, j \leq n)$,第二套中的第 $j$ 个机器人是否可以替换第一套中的第 $i$ 个机器人。

将第 $i$ 个机器人提供的第 $j$ 种营养的量记为 $a_{i, j}$,我们可以得到一个 $n \times n$ 的矩阵 $A$。那么,整套机器人能搭配出任何营养需求等价于将矩阵 $A$ 化为行阶梯形矩阵后拥有 $n$ 个非零行,即该矩阵为满秩矩阵。

由于满秩矩阵即可逆矩阵,矩阵 $A$ 可逆等价于矩阵 $A$ 的行列式值 $|A| \neq 0$,因此,我们的任务是快速求出矩阵 $A$ 在替换了某一行的元素后的行列式的值。不难想到通过行列式按行展开法则来计算行列式的值,即假如替换的是矩阵 $A$ 的第 $i$ 行,那么有(以下用 $A_{i, j}$ 表示矩阵的 $(i, j)$ 元的代数余子式,矩阵的行列标号为 $1 \sim n$):

$$|A| = \sum_\limits{k = 1}^{n} a_{i, k}A_{i, k}$$

其中的 $a_{i, k}(1 \leq k \leq n)$ 为第 $i$ 行替换后的元素值。由于代数余子式 $A_{i, k}$ 的值与第 $i$ 行本身的元素无关,因此我们可以先用 $O(n^3)$ 的时间求出矩阵 $A$ 的伴随矩阵,从而得到矩阵所有元素对应的代数余子式的值。具体地,设矩阵 $A$ 的伴随矩阵为 $A^_$,根据 $A^{-1} = \frac{1}{|A|}A^_$ 可得 $A^* = |A|A^{-1}$,由于可以在 $O(n^3)$ 的时间内求出矩阵 $A$ 的逆矩阵 $A^{-1}$(并顺便求出矩阵 $A$ 的行列式值 $|A|$),因此自然能够在相同的时间内求出伴随矩阵。得到所有元素的代数余子式的值后,我们便能在 $O(n)$ 的时间内求出单次行替换后矩阵的行列式值。一共需要进行 $O(n^2)$ 次替换与判断,故预处理出每个机器人对应的替换集合所需的总时间复杂度为 $O(n^3)$。

预处理完毕后,我们就可以通过求二分图匹配来寻找解的方案。不过,注意到题目要求求出字典序最小的匹配,因此直接通过一次二分图匹配得到的方案并不是我们所需要的答案,我们需要在此基础上再进行一次贪心。具体地,我们从小到大枚举编号 $i$,然后判断在第一套机器人中编号小于 $i$ 的机器人的匹配状态不变的情况下,编号为 $i$ 的机器人能否与编号更优的机器人匹配即可。

总时间复杂度为 $O(n^3)$。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 3e2 + 10, mod = 1e9 + 7;

void add(int& x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int mul(int x, int y) {
  return (long long) x * y % mod;
}

int qpow(int v, int p) {
  int result = 1;
  for (; p; p >>= 1, v = mul(v, v)) {
    if (p & 1) {
      result = mul(result, v);
    }
  }
  return result;
}

int n, a[N][N], b[N][N], inv[N][N], adj[N][N], choice[N], visit[N], tt, answer[N];
vector<int> go[N];

void transform1(int a[N][N], int i, int j) {
  for (int p = 0; p < n; ++p) {
    swap(a[i][p], a[j][p]);
  }
}

void transform2(int a[N][N], int i, int k) {
  for (int p = 0; p < n; ++p) {
    a[i][p] = mul(a[i][p], k);
  }
}

void transform3(int a[N][N], int i, int j, int k) {
  for (int p = 0; p < n; ++p) {
    add(a[i][p], mul(a[j][p], k));
  }
}

void get_adj() {
  int det = 1;
  for (int i = 0; i < n; ++i) {
    inv[i][i] = 1;
  }
  for (int i = 0; i < n; ++i) {
    if (!a[i][i]) {
      int p = i;
      for (int j = i + 1; j < n; ++j) {
        if (a[j][i]) {
          p = j;
        }
      }
      if (p == i) {
        puts("NIE");
        exit(0);
      }
      transform1(a, i, p);
      transform1(inv, i, p);
      det = (mod - det) % mod;
    }
    det = mul(det, a[i][i]);
    int x = qpow(a[i][i], mod - 2);
    transform2(a, i, x);
    transform2(inv, i, x);
    for (int j = i + 1; j < n; ++j) {
      int p = a[j][i];
      transform3(a, j, i, (mod - p) % mod);
      transform3(inv, j, i, (mod - p) % mod);
    }
  }
  for (int i = n - 1; ~i; --i) {
    for (int j = i + 1; j < n; ++j) {
      int p = a[i][j];
      transform3(a, i, j, (mod - p) % mod);
      transform3(inv, i, j, (mod - p) % mod);
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      adj[i][j] = mul(inv[j][i], det);
    }
  }
}

bool find(int u) {
  for (int i = 0; i < go[u].size(); ++i) {
    int v = go[u][i];
    if (visit[v] != tt) {
      visit[v] = tt;
      if (!~choice[v] || find(choice[v])) {
        choice[v] = u;
        return true;
      }
    }
  }
  return false;
}

bool find_better(int u, int down) {
  for (int i = 0; i < go[u].size(); ++i) {
    int v = go[u][i];
    if (visit[v] != tt) {
      visit[v] = tt;
      if (choice[v] == down || (choice[v] > down && find_better(choice[v], down))) {
        answer[u] = v;
        choice[v] = u;
        return true;
      }
    }
  }
  return false;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      scanf("%d", &a[i][j]);
    }
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      scanf("%d", &b[i][j]);
    }
  }
  get_adj();
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int det = 0;
      for (int k = 0; k < n; ++k) {
        add(det, mul(b[j][k], adj[i][k]));
      }
      if (det) {
        go[i].push_back(j);
      }
    }
  }
  memset(choice, -1, sizeof choice);
  int total = 0;
  for (int i = 0; i < n; ++i) {
    ++tt;
    total += find(i);
  }
  if (total != n) {
    puts("NIE");
  } else {
    puts("TAK");
    for (int i = 0; i < n; ++i) {
      ++tt;
      find_better(i, i);
      printf("%d\n", answer[i] + 1);
    }
  }
  return 0;
}
点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Wesley13 Wesley13
2年前
BZOJ4898 & BZOJ5367 & 洛谷3778:[APIO2017]商旅——题解
https://www.lydsy.com/JudgeOnline/problem.php?id4898(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.lydsy.com%2FJudgeOnline%2Fproblem.php%3Fid%3D4898)https://w
Python进阶者 Python进阶者
3个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这