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

大牛们帮忙看看,我第一个用邻接矩阵过了,第二个改用vector做邻接表,死活也WA,

Posted by cactuslrd at 2009-04-01 19:49:43 on Problem 3281
第一道
#include<iostream>
#define inf 1000000000
using namespace std;

int map[550][550];
int f[550][550];
int N,F,D;
int food[110],drink[110];
int fl,dl;
int S,T;
int pre[550];
int que[550];
int d[550];
int ans;

__inline int min(int x,int y)
{
	return x<y?x:y;
}


void slove()
{
int i,j,p,q,now,next;
ans=0;
memset(f,0,sizeof(f));
while(1)
{
p=0;
q=1;
for(i=1;i<=T;i++) d[i]=inf;
for(i=1;i<=T;i++) pre[i]=0;
pre[S]=S; 
que[q]=S;
while(p<q && pre[T]==0)
{
p++;
now=que[p];
for(i=1;i<=T;i++)
{
     
	if (map[now][i] && !pre[i] && f[now][i]!=map[now][i])
	 {
	    que[++q]=i;
		pre[i]=now;
		d[i]=min(d[now],map[now][i]-f[now][i]);
	 }
     if (!pre[i] && f[i][now]>0)
	 {
	    que[++q]=i;
		pre[i]=-now;
		d[i]=min(d[now],f[i][now]);
	 }
}
}
if (pre[T]==0) break;
for(i=T;i!=S;)
{
   if (pre[i]>0)
   {
     f[pre[i]][i]+=d[T];
	 i=pre[i];
   }
   else
   {
     f[i][-pre[i]]-=d[T];
	 i=-pre[i];
   }
}
ans+=d[T];
}
printf("%d\n",ans);
}

int main()
{
int i,j,k;

//freopen("dining.10.in","r",stdin);
scanf("%d %d %d",&N,&F,&D);
memset(map,0,sizeof(map));
for(i=1;i<=N;i++) 
map[F+i][F+N+i]=1;

for(i=1;i<=N;i++)
{
scanf("%d %d",&fl,&dl);
for(j=1;j<=fl;j++) scanf("%d",&food[j]);
for(j=1;j<=dl;j++) scanf("%d",&drink[j]);

for(j=1;j<=fl;j++) 
map[food[j]][F+i]=1;

for(j=1;j<=dl;j++) 
map[F+N+i][F+2*N+drink[j]]=1;

}
S=2*N+F+D+1;
T=S+1;
for(i=1;i<=F;i++) 
map[S][i]=1;

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

slove();
return 0;
}
第二道

#include<iostream>
#include<vector>
#define inf 1000000000
using namespace std;

typedef struct
{
int num,v;
}node;
vector<node> map[550];
//int map[550][550];
int f[550][550];
int N,F,D;
int food[110],drink[110];
int fl,dl;
int S,T;
int pre[550];
int que[550];
int d[550];
int ans;

__inline int min(int x,int y)
{
	return x<y?x:y;
}


void slove()
{
int i,j,p,q,now,next;
ans=0;
memset(f,0,sizeof(f));
while(1)
{
p=0;
q=1;
for(i=1;i<=T;i++) d[i]=inf;
for(i=1;i<=T;i++) pre[i]=0;
pre[S]=S; 
que[q]=S;
while(p<q && pre[T]==0)
{
p++;
now=que[p];
for(i=0;i<map[now].size();i++)
{
    next=map[now][i].num; 
	if (!pre[next] && f[now][next]!=map[now][i].v)
	 {
	    que[++q]=next;
		pre[next]=now;
		d[next]=min(d[now],map[now][i].v-f[now][next]);
	 }
     if (!pre[next] && f[next][now]>0)
	 {
	    que[++q]=next;
		pre[next]=-now;
		d[next]=min(d[now],f[next][now]);
	 }
}
}
if (pre[T]==0) break;
for(i=T;i!=S;)
{
   if (pre[i]>0)
   {
     f[pre[i]][i]+=d[T];
	 i=pre[i];
   }
   else
   {
     f[i][-pre[i]]-=d[T];
	 i=-pre[i];
   }
}
ans+=d[T];
}
printf("%d\n",ans);
}

int main()
{
int i,j,k;
node temp;
//freopen("dining.10.in","r",stdin);
scanf("%d %d %d",&N,&F,&D);
//memset(map,0,sizeof(map));
for(i=0;i<=520;i++) map[i].clear();
for(i=1;i<=N;i++) 
{
	temp.num=F+N+i;
	temp.v=1;
	map[F+i].push_back(temp);
}
for(i=1;i<=N;i++)
{
scanf("%d %d",&fl,&dl);
for(j=1;j<=fl;j++) scanf("%d",&food[j]);
for(j=1;j<=dl;j++) scanf("%d",&drink[j]);

for(j=1;j<=fl;j++) 
{
	temp.num=F+i;
	temp.v=1;
	map[food[j]].push_back(temp);
}
for(j=1;j<=dl;j++) 
{
	temp.num=F+2*N+drink[j];
	temp.v=1;
	map[F+N+i].push_back(temp);
}
}
S=2*N+F+D+1;
T=S+1;
for(i=1;i<=F;i++) 
{
	temp.num=i;
	temp.v=1;
	map[S].push_back(temp);
}
for(i=1;i<=D;i++) 
{
	temp.num=T;
	temp.v=1;
	map[2*N+F+i].push_back(temp);
}
slove();
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