Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:拆点+枚举+网络流(预流推进)还超时啊。。。?谁能帮帮。。

Posted by hao2 at 2009-03-20 22:06:42 on Problem 1815
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator