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 |
求救,用距离标号来写的,无限的TLE,不知道哪里出现死循环了,(code in)#include <stdio.h> #include <memory.h> const int maxn = 510; const int maxint = 1000000000; int N,M,s,t,ans; int cap[maxn][maxn],pre[maxn],vis[maxn],map[maxn][maxn]; void dfs1(int v) { vis[v] = 1; for (int i=0; i<N; i++) { if (vis[i]!=1&& cap[v][i]>0) { dfs1(i); } } } void dfs2(int v) { vis[v] = -1; for (int i=0; i<N; i++) { if (vis[i]==0 && cap[i][v]>0) { dfs2(i); } } } int ret; void maxflow() { int u,i,j,height[maxn] = {0},h,ex; pre[s] = s; u = s; while (height[s] < N) { h = N; for (i=0; i<N; i++) { if (cap[u][i]>0) { if (height[u] == height[i]+1) { pre[i] = u; u = i; if (i==t) { ex = maxint; for (j=t; j!=s; j=pre[j]) if (ex > cap[pre[j]][j]) ex = cap[pre[j]][j]; for (j=t; j!=s; j=pre[j]) cap[pre[j]][j]-=ex,cap[j][pre[j]]+=ex; u = s; ret += ex; } break; } else if (h>height[i]) h = height[i]; } } if (i>=N) height[u] = h+1, u = pre[u]; } } int main() { int i,j,a,b,c; scanf("%d%d",&N,&M); for (i=0; i<M; i++) { scanf("%d%d%d",&a,&b,&c); map[a][b] = 1; cap[a][b] += c; } s = 0; t = N-1; maxflow(); memset(vis,0,sizeof(vis)); dfs1(s); dfs2(t); ans = 0; for (i=0; i<N; i++) { if (vis[i]==1) { for (j=0; j<N; j++) { if (vis[j]==-1 && map[i][j]) { ans++; } } } } printf("%d\n",ans); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator