POJ3041
这道题正解对于像我这种蒟蒻来说比较难以想到。
我们发现每次覆盖的只是一条线上的所有点。那么我们可以把它想象成一个二分图，两个集合分别是横轴和纵轴。
想一想，这实际上是不是就是x轴轴和纵轴的最大匹配？
于是这就变成了一个板子匈牙利算法题目。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctype.h>
#define R register
using namespace std;
inline int read()
{
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
const int maxn=505,maxm=10005;
int n,m;
int mapp[maxn][maxn];
bool vis[maxn];
int match[maxn];
bool find(int x)
{
for(R int i=1;i<=n;i++)
if(mapp[x][i] and vis[i]==0)
{
vis[i]=1;
if(match[i]==0 || find(match[i]))
{
match[i]=x;
return 1;
}
}
return 0;
}
int main()
{
n=read(),m=read();
for(R int i=1;i<=m;i++)mapp[read()][read()]=1;
int ans=0;
for(R int i=1;i<=n;i++)
{
memset(vis,0,sizeof vis);
if(find(i))ans++;
}
printf("%d",ans);
return 0;
}
|
洛谷P1129
这道题也差不多了，\(O(n^2)\)就能过。
也是求x和y轴的最大匹配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctype.h>
#define R register
using namespace std;
inline int read()
{
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
const int maxn=505,maxm=10005;
int n,m;
int mapp[maxn][maxn];
bool vis[maxn];
int match[maxn];
bool find(int x)
{
for(R int i=1;i<=n;i++)
if(mapp[x][i] and vis[i]==0)
{
vis[i]=1;
if(match[i]==0 || find(match[i]))
{
match[i]=x;
return 1;
}
}
return 0;
}
int main()
{
int t=read();
k: while(t--)
{
memset(mapp,0,sizeof mapp);
memset(match,0,sizeof match);
n=read();
for(R int i=1;i<=n;i++)
for(R int j=1;j<=n;j++)mapp[i][j]=read();
int ans=0;
for(R int i=1;i<=n;i++)
{
memset(vis,0,sizeof vis);
if(!find(i)){
printf("No\n");
goto k;
}
}
printf("Yes\n");
}
return 0;
}
|
