#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上的那个模板，不知主函数哪里错了，哪位高手看一下． (1458) 8600 2006-03-02 16:31:29
  • Re:第一次写匹配问题的程序,用的是bbs上的那个模板，不知主函数哪里错了，哪位高手看一下． (23) 8600 2006-03-02 16:33:01
• Re:强悍，我都只会写dfs的，这还有队列的呢…… (1458) byron 2006-11-06 23:43:33