计算最大流我用dinic就AC  但是用距离标号就WA都同样是计算最大流  为什么ISAP不行呢？
难道是算法有错，可做其他最大流两个都可以过呀  这。。。下面提供的那个长数据用我得ISAP确实是过不了 结果是26  但dinic能过  不知道哪里错了  望大侠指点。。。。拜谢了
#include <iostream>
#include <cstring>
using namespace std;

#define MIN(x,y) ((x)<(y)?(x):(y))
const int MAXN = 403;
const int INF = 123456789;

int N,F,D;
int start,end;
int flow[MAXN][MAXN];
int id[MAXN];
int num[MAXN];
int pre[MAXN];

int init()
{
	if(scanf("%d%d%d",&N,&F,&D)!=3)return 0;
	
	int i,k,k1;
	int t;

	memset(flow, 0 ,sizeof(flow));
	for(i=1;i<=N;++i)
	{
		scanf("%d%d",&k,&k1);
		while(k--)
		{
			scanf("%d",&t);
			flow[t][i+F]=1;  //t--i+F  t为食物  i+f为牛 容量为1
		}
		flow[F+i][F+N+i]=1;
		while(k1--)
		{
			scanf("%d",&t);
			flow[F+N+i][2*N+F+t] = 1 ;//f+i --2*N+F+t  前为牛  后为水 容量为1
		}
	}

	for(i=1;i<=F;++i)	flow[0][i]=1;

	for(i=2*N+F+1;i<=2*N+F+D;++i)	flow[i][2*N+F+D+1]=1; 

	start=0;
	end=2*N+F+D+1;
	return 1;
}

int bfs(int s)	//得到各个节点的层次
{
	int i,k,front=0,rear=0;
	int q[MAXN];

	memset( id , -1 , sizeof( id ));

	q[rear++]=s;id[s]=0;

	while( front < rear )
	{
		k = q[ front ++ ];

		for ( i = 0 ; i <= end ; ++ i )
			if( flow[ k ][ i] > 0 && id[ i ] == -1 )
			{
				q[ rear ++ ] = i ;
				id[ i ] =id[ k ] + 1 ;
			}
	}
	return  id[ end ] != -1 ;
}

int dinic(int s,int max)  //求最大流
{
	int t,i;
	int now = max ;
	if( s == end ) return max ;

	for( i = 0 ; i <= end ; ++ i)
	{
		if(flow[ s ][ i ] > 0 && id[ i ] == id[ s ] + 1 )
		{
			t = dinic( i , MIN(flow[s][i] , max ) );
			flow[s][i] -= t;
			flow[i][s] += t;

			max -= t; 
		}
	}
	return now - max;
}

int bfs2(int t)   //反向bfs计算距离标号
{
	int q[MAXN];
	int f=0,r=0;
	int k,i;

	memset(id,-1,sizeof(id));
	memset(num,0,sizeof(num));

	q[r++]=t;id[t]=0;

	while(f<r)
	{
		k=q[f++];
		for(i=0;i<=end;i++)
		{
			if(flow[i][k]>0&&id[i]==-1)  
			{
				id[i]=id[k]+1;
				q[r++]=i;
				num[id[i]]++;  
			}
		}
	}
	return 1;
}

int find(int t)               //查找可行狐
{  
     int i;  
     for(i=1;i<=end;++i)  
     {  
        if(flow[t][i]>0 && id[t]==id[i]+1) return i;  
     }  
     return -1;  
}  

int relabel(int t)            //重新标号     
{  
     int i;  
     int mm = end+2;  
     for(i=0;i<=end;++i)  
     {  
         if(flow[t][i]>0) mm = MIN(mm,id[i]+1);   
     }  
     return mm;  
}  

int maxFlow()  
{  
     int sumflow = 0; 
     int nowflow;  
     int i=start;      //初始化为源点   

     int j;  
     memset(pre,-1,sizeof(pre));      

     while(id[start]<end+1)   
     {  
        j =find(i);     
		
        if(j>=0)        
        {  
            pre[j] = i;  
            i = j;            
            if(i==end)        //找到了一条增广路径    
            {  
                nowflow = INF;  
                for(i=end;i!=start;i=pre[i])
					nowflow=MIN(nowflow,flow[pre[i]][i]);  //求的增广路径的可增流量    

                for(i=end;i!=start;i=pre[i])
					flow[pre[i]][i]-= nowflow, flow[i][pre[i]] += nowflow; //修改残留网络   
                sumflow += nowflow;  

            }  
       }  
       else //可行狐不存在
       {  
            int x = relabel(i);  //重新计算距离标号
            num[x]++;  
            num[id[i]]--;  
            if(num[id[i]]==0) return sumflow;    //优化   如果出现距离标号断了的情况  则说明不可能存在增广路了  直接返回流量
			id[i] = x;  
            if(i!=start) i =pre[i];     //回退 当i不为源点时回退
       }  
     }  
    return sumflow;  
}  

int main()
{
	freopen( "in.txt" , "r" , stdin );
//	while(
		init();//)
	//{
	//	int max=0;
	//	while(bfs(start))max+=dinic(start,INF);
	//	printf("%d\n",max);
		bfs2(end);
		printf("%d\n",maxFlow());
	//}
	return 0;
} 

• Re:已解决！！！！！ (0) ACColor 2010-08-06 16:24:35
• 求助 (28) 392377379 2013-12-09 19:18:58