首页 > 代码库 > 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 }
当然是懒得写缩点啦233

 

BZOJ2208