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 |
Re:拆点+枚举+网络流(预流推进)还超时啊。。。?谁能帮帮。。In Reply To:拆点+枚举+网络流(预流推进)还超时啊。。。?谁能帮帮。。 Posted by:boycott at 2009-03-18 13:54:52 > #include<iostream> > #include<cstdio> > #include<deque> > using namespace std; > const int mxn = 400; > const int mxf = 0x7fffffff; > > int n,np,nc,m; > int c[mxn][mxn],f[mxn][mxn]; > deque<int> act; > int h[mxn]; > int ef[mxn]; > int s,t; > int i,j,k,flow,tp; > > int push_relabel() > { > int i,sum=0,u,v,p; > for(i=0;i<n+n;i++) h[i] = 0; > h[s] = n+n; > memset(ef,0,sizeof(ef)); > ef[s] = mxf; > ef[t] = -mxf; > act.push_front(s); > while(!act.empty()){ > u = act.back(); > act.pop_back(); > for(i=0;i<n+n;i++){ > v = i; > if(c[u][v]<ef[u]) p = c[u][v]; > else p = ef[u]; > if(p>0 && (u==s || h[u]==h[v]+1)){ > c[u][v] -= p; > c[v][u] += p; > if(v==t) sum += p; > ef[u] -= p; > ef[v] += p; > if(v!=s && v!=t) act.push_front(v); > } > } > if(u!=s && u!=t && ef[u]>0){ > h[u]++; > act.push_front(u); > } > } > return sum; > } > int main() > { > memset(f,0,sizeof(f)); > scanf("%d%d%d",&n,&s,&t); > s--;t--; > for(i=0;i<n;++i) > for(j=0;j<n;++j) scanf("%d",&f[i][j]); > for(i=0;i<n;++i) > if(i!=s&&i!=t){ > for(j=0;j<n;++j) > if(f[i][j]){ > f[n+i][j]=2147483647; > f[i][j]=0; > } > f[i][n+i]=1; > } > for(i=0;i<n+n;++i) > for(j=0;j<n+n;++j) c[i][j]=f[i][j]; > flow=push_relabel(); > if(f[s][t]){ > printf("NO ANSWER!\n"); > return 0; > } > if(flow==0){ > printf("0\n"); > return 0; > } > printf("%d\n",flow); > for(i=0;i<n;++i) > if(i!=s&&i!=t&&flow){ > f[i][n+i]=0; > for(j=0;j<n+n;++j) > for(k=0;k<n+n;++k) c[j][k]=f[j][k]; > tp=push_relabel(); > if(flow>tp){ > flow=tp; > printf("%d ",i+1); > } > else{ > f[i][n+i]=1; > } > } > printf("\n"); > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator