测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 测试结果错误.错误结果为:1 正确结果应为:98
测试结果5: 测试结果错误.错误结果为:1 正确结果应为:99
测试结果6: 测试结果错误.错误结果为:1 正确结果应为:100
....
....
#include "stdio.h"
#include "string.h"
int c[201][201]; //容量
int r[201][201]; //残量网络
int f[201][201]; //流量
int N,M;
int marked[201]; //点是否已被访问过
int queue[201];
int pre[201];
int head,rear;
void add_Queue(int e)
{
marked[e]=1;
rear++;
queue[rear]=e;
return ;
}
int del_Queue()
{
int temp=queue[head];
head++;
return temp;
}
int Find() //寻找增广路
{
memset(marked,0,sizeof(marked));
memset(pre,0,sizeof(pre));
int i,temp;
head=1;
rear=0;
add_Queue(0);
while(head<=rear && !marked[N+M+1])
{
temp=del_Queue();
for(i=1;i<=N+M+1;i++)
{
if(r[temp][i]>0 && !marked[i])
{
add_Queue(i);
pre[i]=temp;
}
}
}
return marked[N+M+1];
}
int main()
{
memset(f,0,sizeof(f));
memset(c,0,sizeof(c));
int i,j;
int stu;
int sum=0;
scanf("%d %d",&N,&M);
for(i=1;i<=N;i++)
{
while(1)
{
scanf("%d",&stu);
if(stu==0)
break;
c[i][N+stu]=1;
}
}
for(i=1;i<=N;i++)
c[0][i]=1;
for(i=N+1;i<=N+M;i++)
c[i][N+M+1]=1;
for(i=0;i<=N+M+1;i++)
for(j=0;j<=N+M+1;j++)
r[i][j]=c[i][j];
while(Find())
{
for(i=N+M+1;i>0;i=pre[i])
{
f[pre[i]][i]++; //更新流量
f[i][pre[i]]=-f[pre[i]][i];
r[pre[i]][i]=c[pre[i]][i]-f[pre[i]][i]; //更新残量网络
r[i][pre[i]]=c[i][pre[i]]-f[i][pre[i]];
}
}
for(i=1;i<=N+M+1;i++)
sum+=f[0][i];
printf("%d\n",sum);
return 0;
}