我要啦免费统计
http://acm.pku.edu.cn/JudgeOnline/problem?id=1274
二分最大匹配
最大流用  匈牙利 或者最大流(建图 源点s连上所有的牛,所有的棚连上汇点t)
#include<iostream>
using   namespace  std;
 
#define  MAXN   201 
 
int  uN, vN;   // u,v数目  
 bool  g[MAXN][MAXN]; // g[i][j] 表示 xi与yj相连  
 int  xM[MAXN], yM[MAXN];  //  输出量  
 bool  chk[MAXN];  // 辅助量 检查某轮 y[v]是否被check  
bool  SearchPath( int  u)
{
     
int  v;
     
for  (v = 0 ; v < vN; v ++ ){
         
if  (g[u][v]  &&   ! chk[v]){
            chk[v]  
=   true ;
             
if  (yM[v]  ==   - 1   ||  SearchPath(yM[v])){
                yM[v]  
=  u;
                xM[u]  
=  v;
                 
return   true ;
            } 
        } 
    } 
     
return   false ;

 
 
int  MaxMatch()
{
     
int  u;
     
int  ret  =   0 ;
    memset(xM,  
- 1 ,  sizeof (xM));
    memset(yM,  
- 1 ,  sizeof (yM));
     
for  (u = 0 ; u < uN; u ++ ){
         
if  (xM[u]  ==   - 1 ){
            memset(chk,  
false ,  sizeof (chk));
             
if  (SearchPath(u)) ret ++ ;
        } 
    } 
     
return  ret;

 
int main()
{
    
    
while(scanf("%d%d",&uN,&vN)!=EOF) {
        
int i,j;
        memset(g,
0,sizeof(g));
        
for(i=0;i<uN;i++) {
            
int a,b;
            scanf(
"%d",&a);
            
for(j=0;j<a;j++){
                scanf(
"%d",&b);
                g[i][b
-1]=1;
            }
        }
        printf(
"%d\n",MaxMatch());
    }
    
return 0;
}
 
#include<iostream>
using namespace std;
 
#define MAXN 410
#define inf 2100000000
//传入网络节点数n,容量mat,源点source,汇点sink
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
    
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
    
if (source==sink) return inf;
    
for (i=0;i<n;i++)
        
for (j=0;j<n;flow[i][j++]=0);
    
for (;;){
        
for (i=0;i<n;pre[i++]=0);
        pre[t
=source]=source+1,d[t]=inf;
        
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
            
for (i=0;i<n;i++)
                
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
                    pre[que[q
++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
                
else if (!pre[i]&&(j=flow[i][t]))
                    pre[que[q
++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
        
if (!pre[sink]) break;
        
for (i=sink;i!=source;)
            
if (pre[i]>0)
                flow[pre[i]
-1][i]+=d[sink],i=pre[i]-1;
            
else
                flow[i][
-pre[i]-1]-=d[sink],i=-pre[i]-1;
    }
    
for (j=i=0;i<n;j+=flow[source][i++]);
    
return j;
}
int mat[MAXN][MAXN],flow[MAXN][MAXN];
 
 
int main()
 {
     
int n,m;
     
int s,t;
     
int k,a,b;
     
while(scanf("%d%d",&n,&m)!=EOF){
        memset(mat,
0,sizeof(mat));
        memset(flow,
0,sizeof(flow));
        
for(int i=1;i<=n;i++){
          mat[
0][i]=1;
        }
// s->1--n 
        for(int i = n+1;i <= n+m;i++){
           mat[i][n
+m+1]=1;
        }
//(n+1)--(n+m)->t 
        for(int i=1;i<=n;i++){
           scanf(
"%d",&k);
           
for(int j=0;j<k;j++){
             scanf(
"%d",&a);
             mat[i][n
+a]=1;
           }
        }
        printf(
"%d\n",max_flow(n+m+2,mat,0,n+m+1,flow));
     }
     
return 0;
 }


posted on 2009-02-15 16:18 阅读(1059) 评论(0)  编辑 收藏 引用 所属分类: pku

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理