poj 1274 The Perfect Stall


二分图的最大匹配,加一个源点,这个源点到左边所有顶点加一条边,权值为1. 。同理,加一个终点,所有右边的定点到这个终点有条边,权值为1. 这样二分图的最大匹配就转换成了最大流问题。

#include<iostream>
#include
<queue>
#include
<cstring>
using namespace std;
const int MAX=405;
int cap[MAX][MAX]={0};
int flow[MAX][MAX]={0};
int pre[MAX],m[MAX];
int N, M,S,T;
const int INF=10000000;

int bfs(int s)
{
    memset(m,
0,sizeof m);  
    memset(pre,
0,sizeof pre);
    queue
<int> q;
    q.push(s);
    m[s]
=INF;
    
while(!q.empty())
    {
            
int u=q.front(); q.pop();
            
for(int v=0; v<=N+M+1; v++)
                    
if(!m[v]&&cap[u][v]>flow[u][v])
                    {
                         pre[v]
=u;
                         m[v]
= m[u]>cap[u][v]-flow[u][v]?cap[u][v]-flow[u][v]:m[u];
                         q.push(v);
                    }
    }
    
   
if(m[T]==0)return 0;
   
   
for(int u=T; u!=S ; u=pre[u])
   {
           flow[pre[u]][u]
+=m[T];
           flow[u][pre[u]]
-=m[T];
   }
   
return m[T];
}

int main()
{
    
    
while(cin>>N>>M)
    {    memset(cap,
0,sizeof cap);
         memset(flow,
0,sizeof flow);
         
for(int i=1; i<=N; i++)
         {
            
int c,e;
            cin
>>c;
            
for(int j=1; j<=c; j++)
                   {
                         cin
>>e;
                         e
=e+N;
                         cap[i][e]
=1;
                   } 
         } 
         S
=0
         T
=N+M+1;
         
for(int i=1; i<=N; i++)
            cap[
0][i]=1;
            
         
for(int i=1; i<=M; i++)
            cap[N
+i][T]=1;
    
         
int ans=0;
         
while(1)
         {
            
int temp=bfs(S);
            
if(temp==0)break;
            
else ans+=temp;
         }
    
         cout
<<ans<<endl;
    }   
    system(
"pause");
    
return 0;
}

posted on 2010-08-30 10:09 田兵 阅读(79) 评论(0)  编辑 收藏 引用 所属分类: 图论题


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


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜