#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;
}

• Re:拆点+枚举+网络流(预流推进)还超时啊。。。？谁能帮帮。。 (2021) hao2 2009-03-20 22:06:42
• 终于AC..记录边就行了 (90) boycott 2009-03-25 09:38:29
  • 竟然神奇的AC了！！900+ms (96) swust20064469 2009-06-28 15:30:02