| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
大牛们帮忙看看,我第一个用邻接矩阵过了,第二个改用vector做邻接表,死活也WA,第一道
#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator