Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
原来memset有增大内存的效果:一开始内存为1060k,用了memset后瞬间变为24000+k 神奇呀 #include <cstdio> #include <cstring> #define min(a,b)(a<b?a:b) #define N 10010 #define M 20010 int n, m, dfn[N]= {0}, low[N], h[N], e[M], ne[M], idx, t, num, time ; bool map[20000][20000] = {0}; void add (int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ; } int tarjan (int u, int v) { int i, s = 0 ; dfn[u] = low[u] = ++ time ; for (i = h[u]; i != -1; i = ne[i]) if (!dfn[e[i]]){ t = tarjan (e[i], u) ; low[u] = min(low[u], low[e[i]]) ; if (low[e[i]] > dfn[u]) num += !t, s ++ ; else s += t ;} else if (e[i] != v && dfn[e[i]] < dfn[u]) low[u] = min(low[u], dfn[e[i]]) ; return s ; } int main () { int i, j ; scanf ("%d%d", &n, &m) ; idx = num = time = 0 ; memset (h, -1, sizeof h) ; memset (map, 0, sizeof map) ; while (m -- ){ scanf ("%d%d", &i, &j) ; if (!map[i][j]){ add (i, j) ; add (j, i) ; map[i][j] = map[j][i] = 1 ;}} num += tarjan (1, -1) == 1 ; printf ("%d\n", (num + 1) >> 1) ; return 0 ; } 大家快看呀, 我开了一个381MB的数组,居然status里却写着1000+k Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator