> #include<stdio.h>
> #define MAX 130
> 
> 
> int Bipartite(bool vc [][MAX],int nv1,int nv2) {
>     int i, j, x, n;
>     int q[MAX], prev[MAX], qs, qe;
>     int vm1[MAX], vm2[MAX];
> 
>     n = 0;
>     for( i = 0; i < nv1; i++ ) vm1[i] = -1;
>     for( i = 0; i < nv2; i++ ) vm2[i] = -1;
>     for( i = 0; i < nv1; i++ ) {
>         for( j = 0; j < nv2; j++ ) prev[j] = -2;
>         qs = qe = 0;
>         for( j = 0; j < nv2; j++ ) if( vc[i][j] ) {
>             prev[j] = -1;
>             q[qe++] = j;
>         }
>         while( qs < qe ) {
>             x = q[qs];
>             if( vm2[x] == -1 ) break;
>             qs++;
>             for( j = 0; j < nv2; j++ ) if( prev[j] == -2 && vc[vm2[x]][j] ) {
>                 prev[j] = x;
>                 q[qe++] = j;
>             }
>         }
>         if( qs == qe ) continue;
>         while( prev[x] > -1 ) {
>             vm1[vm2[prev[x]]] = x;
>             vm2[x] = vm2[prev[x]];
>             x = prev[x];
>         }
>         vm2[x] = i;
>         vm1[i] = x;
>         n++;
>     }
>     return n;
> }
> 
> 
> int main()
> {
> 	bool vc[MAX][MAX]={false};
> 	int ca,i,a,b,x,y;
> 	scanf("%d",&ca);
> 	while(ca--)
> 	{
> 		scanf("%d%d",&a,&b);
> 		for(i=1;i<=b;i++)
> 		{
> 			scanf("%d%d",&x,&y);
> 			vc[x-1][y-1]=true;//次两点存在联系，值变为1
> 		}
> 		printf("%d\n",a-Bipartite(vc,a,a));//总的点数减去最大匹配数
> 	}
> 	return 0;
> }
> 
> 
> 

• Re:第一次写匹配问题的程序,用的是bbs上的那个模板，不知主函数哪里错了，哪位高手看一下． (23) 8600 2006-03-02 16:33:01