算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    有N(N<100,000)个人要去M(M<10)个星球,每个人只可以去一些星球,一个星球最多容纳Ki个人。请问是否所有人都可以选择自己的星球...

吐槽:

    1. 虽然是水题,但是测试了一下dinic和匈牙利算法解决多重匹配的效率,还是值得纪念一下的....
    2. hdu上需要用C++交.... 否则会因为读入超时... (害得我对拍+换算法搞了好久,否则昨天就捉好了.... )

算法分析:

    
    直接建立二分图模型,上匈牙利算法....
    匈牙利算法可以解决多重匹配.... 注意不能把可以匹配多个的点分割然后按照正常的二分匹配来做,那样肯定会挂的....
    解决多重匹配就是记录一下多重匹配的点(简称Y方点)已经匹配了Pi个点。如果Pi<Ki那么就直接上了,否则的话继续搜索Yi已经匹配的每一个点并将Yi染色...
    因为Yi搜一次就需要染色了,而且Y方点最多是10个,所以每次找增广路的深度最多是10... 这样就很快了...
    
    最大的一组数据100ms, 用dinic直接没有结果(等的不耐烦了直接ctrl+c了)........
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define re(i,n) for(int i=0;i<n;i++)
 5 const int N = 100005;
 6 const int M = 11;
 7 int yM[M][N];
 8 int tem[M],num[M],chk[M];
 9 int G[N][M];
10 int n,m;
11 bool dfs(int u){
12     re(v,m) if(G[u][v] && !chk[v]){
13         chk[v] =1;
14         if(tem[v] < num[v]){
15             yM[v][tem[v]++] = u;
16             return 1;
17         }
18         else re(i,tem[v])
19             if(dfs(yM[v][i])){
20                 yM[v][i] = u;
21                 return 1;
22             }
23     }
24     return 0;
25 }
26 int main(){
27     while(~scanf("%d%d",&n,&m)){
28         re(i,n) re(j,m) scanf("%d",&G[i][j]);
29         re(i,m) scanf("%d",&num[i]);
30         re(i,m) tem[i] = 0;
31         int flag = 1;
32         re(i,n) {
33             re(j,m) chk[j] = 0;
34             if(!dfs(i)) { flag = 0; break;}
35         }
36         puts(flag?"YES":"NO");
37     }
38 }
39 
posted on 2012-05-06 14:20 西月弦 阅读(1387) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

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