被一道普及组的题卡了这么长时间，不开心。调了两三天，发现cnt=0;放错位置了。
至于原题，COGS
经（简）典（单）的拓扑排序，数据范围还这么小。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> using namespace std; queue <int> q; int n, m, in[1005], b[1005],level; bool map[1005][1005], a[1005]; inline int get_num() { int ans = 0; char tmp; tmp = getchar(); while (tmp > '9' || tmp < '0') tmp = getchar(); while (tmp <= '9'&&tmp >= '0') { ans = ans * 10 + tmp - 48; tmp = getchar(); } return ans; } int main() { freopen("level2013.in", "r", stdin); freopen("level2013.out", "w", stdout); int si, tmp, cnt; n = get_num(); m = get_num(); for (int i = 1; i <= m; i++) { cnt = 0; si = get_num(); memset(a, 0, sizeof(a)); for (int j = 1; j <= si; j++) { tmp = get_num(); b[++cnt] = tmp; a[tmp] = true; } for (int j = b[1]; j <= b[cnt]; j++) { if (!a[j]) { for (int k = 1; k <= cnt; k++) { if (!map[j][b[k]]) { map[j][b[k]] = 1; in[b[k]]++; } } } } } for (int i = 1; i <= n; i++) { if (!in[i]) q.push(i); } while (!q.empty()) { si = q.size(); level++; for (int i = 1; i <= si; i++) { int ti = q.front(); q.pop(); for (int j = 1; j <= n; j++) { if (map[ti][j]) { in[j]--; if (!in[j]) q.push(j); } } } } cout << level << "\n"; return 0; } |
看看你为了减小常数就喜欢用读入优化
这样非常和谐对不对。。