| ||||||||||
| 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