65 条题解

  • 7
    @ 2017-05-08 12:43:35
    /*
    一个很老的经典的二分图的梗了
    看成两部分分别为(1..n)和(1..m)的二分图
    若(x,y)=1 则给x-->y连条边
    问题转化为选出最少的点使以这些点为端点的所有边的集合为所有边的集合
    也就是最小点覆盖数了
    根据König定理我们可以知道 二分图的最大匹配等于这个图的最小点覆盖数
    这个鬼东西自己记下来就好了
    思路很简单
    再简单重述一遍
    就是对于有凸起的格子坐标为(x,y)
    我们就在x,y中连一条边
    然后直接裸的匈牙利算法求个最大匹配就是答案
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    int map[102][102];
    int Link[102]={0};
    bool visit[102];
    int n,m;
    
    bool dfs(int x)
    {
        for(int i=1;i<=m;i++)
            if(!visit[i]&&map[x][i])
            {
                visit[i]=1;
                if(!Link[i]||dfs(Link[i]))
                {
                    Link[i]=x;
                    return true;
                }
            }
        return false;
    }
    
    int main()
    {
        char c;
        int ans=0;
        cin>>n>>m;
        getchar();
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            { 
                cin>>c;
                if (c=='1') 
                    map[i][j]=1;
            }
            getchar();
        }
        for(int i=1;i<=n;i++)
        {
            memset(visit,0,sizeof(visit));
            if(dfs(i))
                ans++;
        }
        cout<<ans<<endl;
        return 0;
    }
         
    
  • 1
    @ 2017-07-10 10:52:54
    哇建图前tot要先从2开始存,mdzz这个地方调了半个小时,这么H2O的dinic能打这么久我也是醉了
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    const int M = 100005;
    const int N = 504;
    const int INF = 1999122700;
    int head[M], to[M], nxt[M], h[M], cnt, tot=1, S, T, n, m;
    int ans = 0;
    int dis[M];
    char mp[N][N];
    void add(int u, int v, int w)
    {
        nxt[++tot] = head[u];
        head[u] = tot;
        to[tot] = v;
        h[tot] = w;
    }
    void insert(int u, int v, int w)
    {
        add(u, v, w);
        add(v, u, 0);
    }
    /*
    void insert(int u,int v,int w){
         add(u,v,w);add(v,u,0);
    }*/
    queue<int> q;
    inline int dfs(int x, int f)
    {
        int w = INF, used = 0;
        if(x == T) return f;
        for(int i = head[x]; i; i = nxt[i])
        {
            if(dis[to[i]] == dis[x]+1 && h[i])
            {
                w = dfs(to[i], min(f-used, h[i]));
                h[i] -= w;
                h[i^1] += w;
                used += w;
                if(used==f) return f;
            }
        }
        if(!used) dis[x] = -1;
        return used;
    }/*
    int dfs(int x,int f)
    {
        int w=INF,used=0;
        if(x==T)return f;
        for(int i=head[x];i;i=nxt[i]){
            if(dis[to[i]]==dis[x]+1&&h[i]){
               w=dfs(to[i],min(f-used,h[i]));
               h[i]-=w;
               h[i^1]+=w;
               used+=w;if(used==f)return f;
            }
        }
        if(!used)dis[x]=-1;
        return used;
    }*/
    
    inline bool bfs()
    {
        memset(dis, -1, sizeof(dis));
        q.push(S);
        dis[S] = 0;
        while(!q.empty())
        {
            int tmp = q.front();
            q.pop();
            for(int i = head[tmp]; i; i = nxt[i])
                if(h[i] && dis[to[i]] == -1)
                {
                    dis[to[i]] = dis[tmp] + 1;
                    q.push(to[i]);
                }
        }
        if(dis[T] != -1) return 1;
        return 0;
    }/*
    bool bfs(){
         memset(dis,-1,sizeof(dis));
         q.push(S);dis[S]=0;
         while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=head[x];i;i=nxt[i]){
                if(h[i]&&dis[to[i]]==-1){
                    dis[to[i]]=dis[x]+1;
                    q.push(to[i]);
                }
            }
         }
         if(dis[T]!=-1)return 1;
         return 0;
    }*/
    int main()
    {
        cin>>n>>m;
        for(int i=1; i<=n; i++)scanf("%s", mp[i]+1);
        S = 0;
        T = 501;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(mp[i][j] == '1') insert(i, j+n, 1);
        for(int i=1; i<=n; i++) insert(S, i, 1);
        for(int i=1; i<=m; i++) insert(i+n, T, 1);
        while(bfs())
            ans += dfs(S, INF);
        printf("%d\n", ans);
        return 0;
    }
    
    
  • 1
    @ 2017-06-09 15:01:34
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <limits>
    #include <string>
    #include <vector>
    #include <deque>
    using namespace std;
    
    int n,m;
    vector<int> l;
    vector<vector<bool> > a;
    vector<bool> c;
    
    void c_v_1()
    {
        l.resize(0);
        a.resize(0);
    }
    
    int find_1(int now)
    {
        for (int i=1;i<=m;i++)
            if (a[now][i]==1&&c[i]==0)
            {
                int temp=l[i];
                l[i]=now,c[i]=1;
                if (temp>0)
                {
                    if (find_1(temp)==1)
                        return 1;
                }
                else
                    return 1;
                l[i]=temp;
            }
        return 0;
    }
    
    int work_1()
    {
        int ans=0;
        for (int i=1;i<=n;i++)
        {
            c.resize(0);
            c.resize(m+1,0);
            ans+=find_1(i);
        }
        return ans;
    }
    
    int main()
    {
        while (~scanf("%d%d",&n,&m))
        {
            c_v_1();
            a.resize(n+1);
            for (int i=1;i<=n;i++)
            {
                a[i].resize(m+1,0);
                char temp;
                scanf("%c",&temp);
                for (int j=1;j<=m;j++)
                {
                    scanf("%c",&temp);
                    a[i][j]=temp-'0';
                }
            }
            l.resize(m+1,0);
            printf("%d\n",work_1());
        }
    }
    
  • 1
    @ 2017-05-23 20:43:42

    a[i][j]有直接i点连接j点;
    求最大匹配;
    为什么?
    因为在这个图里,每一条变现代标一个点;
    我们删掉一行一列,等同删去一个点即他相连的边;
    所以我们求最小覆盖;
    就是最大匹配嘛;

  • 0
    @ 2022-07-18 10:05:16
    /*
    一个很老的经典的二分图的梗了
    看成两部分分别为(1..n)和(1..m)的二分图
    若(x,y)=1 则给x-->y连条边
    问题转化为选出最少的点使以这些点为端点的所有边的集合为所有边的集合
    也就是最小点覆盖数了
    根据König定理我们可以知道 二分图的最大匹配等于这个图的最小点覆盖数
    这个鬼东西自己记下来就好了
    思路很简单
    再简单重述一遍
    就是对于有凸起的格子坐标为(x,y)
    我们就在x,y中连一条边
    然后直接裸的匈牙利算法求个最大匹配就是答案
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    int map[102][102];
    int Link[102]={0};
    bool visit[102];
    int n,m;
    
    bool dfs(int x)
    {
        for(int i=1;i<=m;i++)
            if(!visit[i]&&map[x][i])
            {
                visit[i]=1;
                if(!Link[i]||dfs(Link[i]))
                {
                    Link[i]=x;
                    return true;
                }
            }
        return false;
    }
    
    int main()
    {
        char c;
        int ans=0;
        cin>>n>>m;
        getchar();
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            { 
                cin>>c;
                if (c=='1') 
                    map[i][j]=1;
            }
            getchar();
        }
        for(int i=1;i<=n;i++)
        {
            memset(visit,0,sizeof(visit));
            if(dfs(i))
                ans++;
        }
        cout<<ans<<endl;
        return 0;
    }
         
    
    
  • 0
    @ 2017-04-30 16:49:41

    最小二分图匹配例题,很裸很裸那种

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int match[11000];
    bool chw[11000],mp[110][110];
    char st[110][110];
    int n,m;
    int findmuniu(int x)
    {
        for(int i=1;i<=m;i++)
            if(mp[x][i]==true)
                if(chw[i]==true)
                {
                    chw[i]=false;
                    if(match[i]==0||findmuniu(match[i])==true)
                    {
                        match[i]=x;
                        return 1;
                    }
                }
        return 0;
    }
    int main()
    {
        memset(match,0,sizeof(match));
        memset(mp,false,sizeof(mp));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%s",st[i]+1);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(st[i][j]=='1')
                    mp[i][j]=true;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(chw,true,sizeof(chw));
            if(findmuniu(i)==true)ans++;
        }
        printf("%d\n",ans);
        return 0;
    }
    
  • 0
    @ 2016-09-09 20:43:41

    http://blog.sina.com.cn/s/blog_51cea4040100h152.html
    ```
    c++
    //分别以行与列来构成二分图的x集与Y集,再用最小点覆盖=最大匹配
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int n,m;
    char g[110][110];
    int match[110]={0};
    int use[110];

    int dfs(int x){
    int i;
    for(i=1;i<=m;i++){
    if(g[x][i]=='1'&&!use[i]){
    use[i]=1;
    if(match[i]==0||dfs(match[i])){
    match[i]=x;
    return 1;
    }
    }
    }
    return 0;
    }

    int main(){
    //freopen("CoVH.txt","r",stdin);
    int i,j,sum=0;
    cin>>n>>m;
    for(i=1;i<=n;i++){
    for(j=1;j<=m;j++){
    cin>>g[i][j];
    }
    }
    for(i=1;i<=n;i++){
    for(j=1;j<=m;j++)
    use[j]=0;
    if(dfs(i)) sum++;
    }
    cout<<sum;
    return 0;
    }
    ```

  • 0
    @ 2016-07-17 09:12:06
    var i,j,k,l,n,m,ans:longint;
        map:array[0..110,0..110]of boolean;
        a:array[0..110,0..110]of char;
        used:array[0..110]of boolean;
        w:array[0..1000]of longint;
    function find(x:longint):boolean;
    var i,j:longint;
    begin
        find:=false;
        for j:=1 to m do
        begin
            if map[x,j]and( not used[j])then
            begin
                used[j]:=true;
                if (w[j]=0)or(find(w[j])) then
                begin
                    w[j]:=x;
                    exit(true);
                end;
            end;
        end;
    end;
    
    begin
        readln(n,m);
        for i:=1 to n do
        begin
            for j:=1 to m do
            begin
                read(a[i,j]);
                if a[i,j]='1' then
                begin
    
                    map[i,j]:=true;
                end;
            end;
            readln;
        end;
    //    fillchar(pd,sizeof(pd),true);
        for i:=1 to n do
        begin
            fillchar(used,sizeof(used),false);
            if find(i) then inc(ans);
        end;
        j:=1;
        writeln(ans);
    end.
    
  • 0
    @ 2016-06-18 13:15:42

    '''pascal
    type
    edge=record
    x,y,next:Longint;
    end;
    var
    e:array[1..10000]of edge;
    link,ls:array[1..100]of longint;
    v:array[1..100]of boolean;
    maxE,n,m:longint;
    procedure add(x,y:longint);
    begin
    inc(maxE);
    e[maxE].x:=x;
    e[maxE].y:=y;
    e[maxE].next:=ls[x];
    ls[x]:=maxE;
    end;
    function find(x:longint):boolean;
    var
    i,k:longint;
    begin
    find:=true;
    i:=ls[x];
    while i>0 do
    with e[i] do
    begin
    if not v[y] then
    begin
    k:=link[y];
    link[y]:=x;
    v[y]:=true;
    if (k=0)or find(k) then exit;
    link[y]:=k;
    end;
    i:=next;
    end;
    find:=false;
    end;
    procedure main;
    var
    i,ans:longint;
    begin
    ans:=0;
    fillchar(link,sizeof(link),0);
    for i:=1 to n do
    begin
    fillchar(v,sizeof(v),false);
    if find(i) then inc(ans);
    end;
    writeln(ans);
    end;
    procedure init;
    var
    i,j:longint;
    s:string;
    begin
    readln(n,m);
    for i:=1 to n do
    begin
    readln(s);
    for j:=1 to m do
    if s[j]='1' then
    add(i,j);
    end;
    end;
    begin
    init;
    main;
    end.
    ```

  • 0
    @ 2015-07-29 15:32:44

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N=100+10;

    char num[N][N];
    int use[N];
    int g[N];
    int n,m;

    bool hungry(int x)
    {
    for(int i=1; i<=m; i++)
    if(num[x][i] == 1 && use[i] == 0){

    use[i]=1;
    if(g[i] == 0 || hungry(g[i])){

    g[i] = x;
    return true;
    }
    }
    return false;
    }

    int main()
    {

    int all=0;
    int all2=0;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    cin>>num[i];
    for(int i=1; i<=n; i++)
    for(int j=m; j>=1; j--)
    num[i][j]=num[i][j-1]-'0';
    for(int i=1; i<=n; i++){
    memset(use,0,sizeof(use));
    if(hungry(i))
    all++;
    }
    cout<<all;
    system("pause");
    return 0;
    }
    匈牙利

  • 0
    @ 2015-07-09 01:37:13

    P1204CoVH之柯南开锁
    Accepted

    记录信息

    评测状态 Accepted
    题目 P1204 CoVH之柯南开锁
    递交时间 2015-07-09 01:36:25
    代码语言 C++
    评测机 VijosEx
    消耗时间 15 ms
    消耗内存 328 KiB
    评测时间 2015-07-09 01:36:34

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 328 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 328 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 328 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 324 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 328 KiB, score = 10

    测试数据 #5: Accepted, time = 0 ms, mem = 328 KiB, score = 10

    测试数据 #6: Accepted, time = 0 ms, mem = 324 KiB, score = 10

    测试数据 #7: Accepted, time = 0 ms, mem = 328 KiB, score = 10

    测试数据 #8: Accepted, time = 15 ms, mem = 328 KiB, score = 10

    测试数据 #9: Accepted, time = 0 ms, mem = 328 KiB, score = 10

    Accepted, time = 15 ms, mem = 328 KiB, score = 100

    代码

    #include <iostream>
    #include <stdio.h>
    #include <string.h>

    using namespace std;

    int x , y;
    char a[100 + 2][100 + 2];
    int i , j;
    int graph[100 + 2][100 + 2];
    int ans1 , ans2;
    int use[100 + 2];
    int match[100 + 2];

    int min( int a , int b )
    {
    if( a > b )
    return b;
    return a;
    }

    bool hungary( int k , int len )
    {
    int i;
    for( i = 0 ; i < len ; i++ )
    if( !use[i] && graph[k][i] )
    {
    use[i] = 1;
    if( !match[i] || hungary( match[i] , len ) )
    {
    match[i] = k;
    return 1;
    }
    }
    return 0;
    }

    int main()
    {
    scanf( "%d %d" , &x , &y );
    for( i = 0 ; i < x ; i++ )
    scanf( "%s" , a[i] );
    for( i = 0 ; i < x ; i++ )
    for( j = 0 ; j < y ; j++ )
    if( a[i][j] == '1' )
    graph[i][j] = 1;
    for( i = 0 ; i < x ; i++ )
    {
    memset( use , 0 , sizeof( use ) );
    if( hungary( i ,y ) )
    ans1++;
    }
    memset( graph , 0 , sizeof( graph ) );
    for( i = 0 ; i < x ; i++ )
    for( j = 0 ; j < y ; j++ )
    if( a[i][j] == '1' )
    graph[j][i] = 1;
    memset( match , 0 , sizeof( match ) );
    for( i = 0 ; i < y ; i++ )
    {
    memset( use , 0 , sizeof( use ) );
    if( hungary( i , x ) )
    ans2++;
    }
    cout << min( ans1 , ans2 ) << endl;
    return 0;
    }
    居然要两次

  • 0
    @ 2014-06-16 21:40:59

    读字符一定要过行!否则要挂……我逗比

  • 0
    @ 2013-11-03 20:14:53

    vijos给我随机一题,一看就贪心,结果只过四个点···看题解才知道二分图最大匹配,万恶的随机。

  • 0
    @ 2012-10-18 18:11:54

    01

    program _1204;

    02

    var

    03

      g:array[0..120,0..120]of boolean;

    04

      h:array[0..120]of boolean;

    05

      mat:array[0..120]of longint;

    06

      ans,n,m,i,j,a,b:longint;c:char;

    07

    function dfs(a:longint):boolean;

    08

    var

    09

      i,t:longint;

    10

    begin

    11

      for i:=1 to b do

    12

        if (g[a,i])and(not h[i]) then

    13

          begin

    14

            h[i]:=true;

    15

            if (mat[i]=0)or(dfs(mat[i])) then

    16

              begin

    17

                mat[i]:=a;

    18

                exit(true);

    19

              end;

    20

          end;

    21

      exit(false);

    22

    end;

    23

    begin        

    24

      readln(n,m);

    25

      if n>m then b:=n else b:=m;

    26

      for i:=1 to n do

    27

        begin

    28

          for j:=1 to m do

    29

            begin

    30

              read(c);

    31

              if ord(c)=ord('1') then g:=true;

    32

            end;

    33

          readln;

    34

        end;

    35

      ans:=0;

    36

      for i:=1 to n do

    37

        begin

    38

          fillchar(h,sizeof(h),false);

    39

          if dfs(i) then inc(ans);

    40

        end;

    41

      writeln(ans);

    42

    end.

  • 0
    @ 2009-10-29 10:06:37

    本来只是想试下。。。

    贪心竟然AC了。。。

    第500个- -

  • 0
    @ 2009-10-24 16:11:07

    啊......

    匈牙利居然有些挂了...

  • 0
    @ 2009-10-09 16:38:18

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    二分图匹配

    由于这道题 我的AC 率上升一点 嘿嘿

  • 0
    @ 2009-09-18 20:36:42

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    二分图的最小覆盖

  • 0
    @ 2009-09-15 19:43:56

    用贪心可过4个点,悲剧

信息

ID
1204
难度
5
分类
图结构 | 二分图 点击显示
标签
递交数
1511
已通过
521
通过率
34%
被复制
7
上传者