题目
一个n*n的方阵，有m个关键点，一次只能够选择hack一行或一列的点，每行或每列最多只能够被hack一次，每个关键点最多只能够被hack一次。 求最多能够hack多少次。 n<=1000,m<=4000.
题解
看错题了。看错2次。 第一次看错题，以为hack一次是指hack一排点。一次hack只能够hack一个点。 第二次看错题，以为一个点至少要被hack一次。 如果是这样子的话，两排点直接并查集就好了。然后每个连通块要么选行，要么选列。 实际上，答案是最大独立集的个数. 最大独立集，也就是所有顶点数-最小顶点覆盖。最大独立集中，点两两之间没有边。 最小顶点覆盖，用这些点就能够覆盖完所有的边。 匈牙利算法的时间复杂度
O
(
n
m
)
O(nm)
O(nm) 菜鸡应该重讲匈牙利算法。 对于每个点，开始找增广路，如果能够找到就继续找，匹配的边变成未匹配的，未匹配的边变成匹配的。 在从起点x开始寻找增广路的过程中，每个点最多只会在增广路里出现1次。所以用bool数组判断一下就好，但考虑到时间复杂度问题，将bool数组换成染色数组即可。
匈牙利算法代码
bool find(int x
){
int i
;
bz
[x
]=j
;
for(i
=head
[x
];i
;i
=edge
[i
].next
)
if(!pre
[edge
[i
].to
]||(bz
[pre
[edge
[i
].to
]]!=j
&&find(pre
[edge
[i
].to
]))){
pre
[edge
[i
].to
]=x
;
return 1;
}
return 0;
}
严肃检讨
为什么会看错题？ 一开始由于看错了第一次题，就有一点慌了，因为放在了NOIP第一题的位置。 一般8:45就看完3道题目了，至少看完第一题了吧。就是一点点意思没有get准，结果就出了大问题。 HOW TO DO WITH?
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 2010
#define M 4010
#define P(a) putchar(a)
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std
;
struct note
{
int to
,next
;
}edge
[M
];
int tot
,head
[N
];
int pre
[N
],bz
[N
];
int n
,m
,i
,j
,lim
,ans
;
int x
,y
;
int read(){
int fh
=0,rs
=0;char ch
=0;
while((ch
<'0'||ch
>'9')&&(ch
^'-'))ch
=getchar();
if(ch
=='-')fh
=1,ch
=getchar();
while(ch
>='0'&&ch
<='9')rs
=(rs
<<3)+(rs
<<1)+(ch
^'0'),ch
=getchar();
return fh
?-rs
:rs
;
}
void write(int x
){
if(x
>9)write(x
/10);
P(x
%10+'0');
}
bool find(int x
){
int i
;
bz
[x
]=j
;
for(i
=head
[x
];i
;i
=edge
[i
].next
)
if(!pre
[edge
[i
].to
]||(bz
[pre
[edge
[i
].to
]]!=j
&&find(pre
[edge
[i
].to
]))){
pre
[edge
[i
].to
]=x
;
return 1;
}
return 0;
}
void lb(int x
,int y
){
edge
[++tot
].to
=y
;
edge
[tot
].next
=head
[x
];
head
[x
]=tot
;
}
int main(){
n
=read(),m
=read();
fo(i
,1,m
){
x
=read(),y
=read();
lb(x
,y
+n
);
}
fo(j
,1,n
)if(find(j
))ans
++;
ans
=((n
<<1)-ans
)*n
;
write(ans
);
return 0;
}
