首页 > 代码库 > BZOJ2208
BZOJ2208
LINK:http://www.lydsy.com/JudgeOnline/problem.php?id=2208
MD水题
正解应该是Trajan缩点+递推
但是暴力O(nm)都能跑10s内
这题就太思博了吧
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define Maxlen (50005 << 2) * 300 4 char buf[Maxlen], *c = buf; 5 int Len; 6 7 void init() { 8 Len = fread(c, 1, Maxlen, stdin); 9 buf[Len] = ‘\0‘;10 }11 12 template <typename T>13 inline T read() {14 register T x = 0, f = 1;15 while (!isdigit(*c)) {16 if (*c == ‘-‘)f = -1; ++c;17 }18 while (isdigit(*c)) {19 x = x * 10 + *c - ‘0‘; ++c;20 }21 return x * f;22 }23 24 template <typename T>25 inline T sread() {26 register T x = 0, f = 1;27 while (!isdigit(*c)) {28 if (*c == ‘-‘)f = -1; ++c;29 }30 x = *c - ‘0‘; ++c;31 return x * f;32 }33 34 #define read() read<int>()35 #define sread() sread<int>()36 /*------------------------------template------------------------------*/37 38 int visited[2020];39 int n, cnt = 0;40 vector<int> edge[2020];41 int dfs(int k) {42 int ret = 0;43 for (int i = 0; i < edge[k].size(); i ++) 44 if (!visited[edge[k][i]]){45 visited[edge[k][i]] = 1;46 ret += dfs(edge[k][i]) + 1;47 }48 return ret;49 }50 51 int main() {52 init();53 n = read();54 for (int i = 1; i <= n; i ++) {55 for (int j = 1; j <= n;j ++) {56 int x = sread();57 if (x) {58 edge[i].push_back(j);59 }60 }61 } int ans = 0;62 for (int i = 1; i <= n; i ++) {63 memset(visited, 0, sizeof(visited));64 visited[i] = 1;65 ans += dfs(i) + 1;66 }67 printf("%d\n", ans);68 }
BZOJ2208
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。