题意：  有 n 条鱼，雄的会攻击他认为是雌的鱼，一条鱼一旦被攻击，就会生下一定数量的孩子，每条鱼只能被攻击一次，

　　　　问最后最多可以生下多少孩子。

分析： 因为每条鱼只能被攻击一次，正好符合二分图的性质，此题只要找出完全匹配下的最优匹配即可。

模板一：

#include
      
       #include
       
        #define INF 0x1f1f1f1fint sx[101],sy[101];int lx[101],ly[101];char a[102][102];int map[102][102];int link[101];int va[101];int n,dmin;int find(int x){    int i,tmp;    sx[x]=1;    for(i=1;i<=n;i++)    if(!sy[i])    {        tmp=lx[x]+ly[i]-map[x][i];        if(tmp==0)        {            sy[i]=1;            if(link[i]==0||find(link[i]))            {                link[i]=x;                return 1;            }        }        else if(tmp
        
         lx[i])            lx[i]=map[i][j];    }    memset(link,0,sizeof(link));    for(v=1;v<=n;v++)    {        memset(sx,0,sizeof(sx));        memset(sy,0,sizeof(sy));        while(1)        {            dmin=INF;            if(find(v))             break;            for(i=1;i<=n;i++)            {                if(sx[i]) {  lx[i]-=dmin;  sx[i]=0;  }                if(sy[i]) {  ly[i]+=dmin;  sy[i]=0;  }            }        }    }    for(i=1;i<=n;i++)        sum+=map[link[i]][i];    return sum;}int main(){    int i,j;    while(scanf("%d",&n),n)    {        for(i=1;i<=n;i++)            scanf("%d",&va[i]);        for(i=1;i<=n;i++)        {            scanf("%s",a[i]+1);            for(j=1;j<=n;j++)            {                map[i][j]=a[i][j]-'0';                if(map[i][j])                    map[i][j]=va[i]^va[j];            }        }        printf("%d\n",KM());    }    return 0;}
        
       
      

 

 模板二：

#include
      
       #include
       
        #define INF 0x1f1f1f1f#define clr(x)memset(x,0,sizeof(x))int link[111];int sx[111],sy[111];int lx[111],ly[111];char a[111][111];int map[111][111];int va[111];int n;int find(int x){    int i;    sx[x]=1;    for(i=1;i<=n;i++)    {        if(!sy[i]&&lx[x]+ly[i]==map[x][i])        {            sy[i]=1;            if(link[i]==0||find(link[i]))            {                link[i]=x;                return 1;            }        }    }    return 0;}int KM(){    int v,i,j,sum=0,dmin;    for(i=1;i<=n;i++)    {        lx[i]=0;        ly[i]=0;        for(j=1;j<=n;j++)            if(map[i][j]>lx[i])            lx[i]=map[i][j];    }    clr(link);    for(v=1;v<=n;v++)    {        clr(sx);  clr(sy);        while(1)        {            if(find(v))break;            dmin=INF;            for(i=1;i<=n;i++)            if(sx[i])            for(j=1;j<=n;j++)            if(!sy[j]&&lx[i]+ly[j]-map[i][j]