题解 - Vijos

7

PowderHan LV 10 @ 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

HeJiaJun LV 9 @ 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

Sky1231 (sky1231) LV 10 @ 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());
    }
}

sky1231 @ 2017-06-09 15:01:59

很H2O的题

1

largecube LV 8 @ 2017-05-23 20:43:42

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

0

niujinyu LV 10 @ 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

limuye LV 9 @ 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

937337156 LV 8 @ 2016-11-08 21:39:30

C++题解+代码
http://www.cnblogs.com/937337156Zhang/p/6044771.html

0

wuwangmao LV 8 @ 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

yingjiangyu LV 9 @ 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

jpwang LV 8 @ 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

linhui LV 9 @ 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

nzhtl1477 LV 10 @ 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

freefood LV 10 @ 2014-06-16 21:40:59

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

0

A渣菌 LV 4 @ 2013-11-03 20:14:53

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

0

Dungeon LV 8 @ 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

coLor_fish9 LV 10 @ 2009-10-29 10:06:37

本来只是想试下。。。

贪心竟然AC了。。。

第500个- -

0

Matt LV 10 @ 2009-10-24 16:11:07

啊......

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

0

陈亮宇 LV 10 @ 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

xianweizhao LV 5 @ 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

zhanghanyuan LV 10 @ 2009-09-15 19:43:56

用贪心可过4个点,悲剧

题解

65 条题解

CoVH之柯南开锁

信息

状态

开发

支持

题解

65 条题解

CoVH之柯南开锁

信息

状态

开发

支持

还没有账户？

登录