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

哪位大侠进来看看，为什么呀！

Posted by ACColor at 2010-08-06 16:09:19 on Problem 3281
```计算最大流我用dinic就AC  但是用距离标号就WA都同样是计算最大流  为什么ISAP不行呢？

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

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

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