请问哪位大虾能帮忙优化一下？
我用STL里的表容器LIST,二维表容器，算法是算法导论里的重标记与前移算法，效率（n^3）,按理不超时的，表操作也是常数级的啊，怎么会超呢？
#define N 105

list<list<int> >L;
int s,t,n;
int e[N],h[N];
int f[N][N],c[N][N];
int maxflow;
int current[N];

void input(int node,int np,int nc,int m)
{	int a,b,c0;int i;
	n = node+2;
	s = 0; t = node+1; maxflow = 0;
	fill(c[0],c[N],0);
	fill(f[0],f[N],0);
	for (i = 0 ; i < m  ;i++)
	{
		while(getchar()!='(');
		scanf("%d,%d)%d",&a,&b,&c0);
		c[a+1][b+1] = c0;
	}
	for (i = 0 ; i < np ; i++)
	{
		while(getchar()!='(');
		scanf("%d)%d",&b,&c0);
		c[s][b+1] = c0;
	}
	for (i = 0 ; i < nc ; i++)
	{
		while(getchar()!='(');
		scanf("%d)%d",&b,&c);
		c[b+1][t] = c0;
	}
}
void Init_Preflow()
{		
	fill(e,e+N,0);
	fill(h,h+N,0);
	h[s] = n;		//n从0到t
	for(int i = 0;i < n; i++)
	{	if(c[s][i]){
			f[s][i] = c[s][i];
			f[i][s] = -c[s][i];
			e[i] = c[s][i];
			e[s] -= c[s][i];
		}
	}
}
void Creat_List()
{	list<int>adj;int i,j;
	L.clear();
	for(i = 1; i < t; i++){
		adj.clear();
		for(j = 0; j <= t; j++){	
			if( (c[i][j]||c[j][i]) && i != j)//自环自相抵消
				adj.push_back(j);
		}
		if(adj.size())	
		{	adj.push_back(i);
			L.push_back(adj);
		}
	}//make L 拓补表	
}
void Relabel(list<int>adj)
{
	//Applies when: u is overflowing and for all v in V such that (u,v) is in Ef, 
	//            we have h[u] <= h[v]. 
	//Action: h[u] = 1 + min{h[v] : (u,v) in Ef 
	list<int>::iterator it;
	int u = adj.back();int v;int min = 2*n;
	for(it = adj.begin(); *it != u;it++){
		v = *it;
		if(c[u][v] > f[u][v])
			min = min<h[v]?min:h[v];
	}
	h[u] = min + 1;
}
void Push(int u,int v)
{
	//Applies when: u is overflowing, cf[u][v]>0, and h[u] = h[v] +1. 
	//cf[u][v] = c[u][v] - f[u][v]; 
	//Action: Push df[u][v] = min{e[u], cf[u][v]) units of flow from u to v
	int Cf = c[u][v] - f[u][v];
	int Df = e[u]<Cf ? e[u]:Cf;
	f[u][v] += Df;
	f[v][u] = -f[u][v];
	e[u] -= Df;
	e[v] += Df;
}
void Discharge(list<int>adj)
{
	int v;list<int>::iterator it = adj.begin();
	int u = adj.back();
	current[u] = adj.front();
	while(e[u] > 0){
		v = current[u];
		if(v == u){
			Relabel(adj);
			current[u] = adj.front();
			it = adj.begin();
		}
		else if(c[u][v] > f[u][v] && h[u] == h[v]+1)
			Push(u,v);
		else {
			current[u] = *(++it);
		}
	}
}
void Relabel_To_Front()
{
	list<list<int> >::iterator iter;list<int>adj;
	int u;	int old_height;
	iter = L.begin(); 
	while(iter != L.end())
	{	adj = *iter;
		u = adj.back();
		old_height = h[u];//各点邻接表父结点放在back
		Discharge(adj);
		if(h[u] > old_height){
			L.push_front(adj);
			L.erase(iter);
			iter = L.begin();
		}
		iter++;
	}
}
	
int main()
{	
	int node,np,nc,m;
	while(scanf("%d%d%d%d",&node,&np,&nc,&m)>0)
	{
		input(node,np,nc,m);
		Init_Preflow();
		Creat_List();
		Relabel_To_Front();
		maxflow = e[t];
		printf("%d\n",maxflow);
	}
	return 1;
}

• Re:用STL里的二维LIST超时了 (6) lh0823 2008-10-06 16:11:45