例题
洛谷 P1894 https://www.luogu.org/problemnew/show/P1894
分析:
裸题, 牛栏作为一个点集, 牛作为另一个, 牛喜欢牛栏则从牛向牛栏连一条边跑匈牙利就得了, 邻接表开大点
- #include<bits/stdc++.h>
- #define MAXN (2000+5)
- using namespace std;
- inline int read(){
- int cnt=0,f=1;char c;
- c=getchar();
- while(!isdigit(c)){
- if(c=='-')f=-f;
- c=getchar();
- }
- while(isdigit(c)){
- cnt=cnt*10+c-'0';
- c=getchar();
- }
- return cnt*f;
- }
- int n,m,nxt[2*MAXN],first[2*MAXN],to[2*MAXN],match[2*MAXN],x,y,ans,tot,res;
- bool vis[2*MAXN];
- void add(int x,int y){
- nxt[++tot]=first[x];
- first[x]=tot;
- to[tot]=y;
- }
- int find(int u){
- for(register int i=first[u];i;i=nxt[i]){
- int v=to[i];
- if(vis[v])continue;
- else {
- vis[v]=true;
- if(match[v]==-1||find(match[v])) {
- match[v]=u;
- match[u]=v;
- return 1;
- }
- }
- }
- return 0;
- }
- int hungary(){
- for(register int i=1;i<=n;i++){
- for(register int j=1;j<=2*n+1;j++)vis[j]=false;
- if(match[i]==-1)ans+=find(i);
- }
- return ans;
- }
- int main(){
- n=read();m=read();
- for(register int i=1;i<=n+m;i++)match[i]=-1;
- for(register int i=1;i<=n;i++){
- x=read();
- for(register int j=1;j<=x;j++){
- y=read();add(i,y+n);
- }
- }
- printf("%d",hungary());
- return 0;
- }
题目链接:
洛谷 P1129 https://www.luogu.org/problemnew/show/P1129
分析:
行和列分别作为两边的点, 将原图的点作为边建图
因为行和列的交换并不会改变图的形态而只是交换编号, 所以对最终答案没有影响
所以读入图的时候如果 Map[i,j]==1 就从 i 往 j 连一条边
然后跑最大匹配就可以了, 跑完若 ans==n 则说明所有行和列都有对应匹配, 那么说明有方案, 如果 ans<n 说明不是所有的行和列都能有对应匹配, 所以就不能通过变换达成对角线 (每行每列都有匹配且不和其他行 / 列的匹配冲突), 说明没有方案
多组数据, 记得初始化
代码:
- #include<bits/stdc++.h>
- #define N (20000+5)
- #define M (200000+5)
- using namespace std;
- inline int read(){
- int cnt=0,f=1;char c;
- c=getchar();
- while(!isdigit(c)){
- if(c=='-')f=-f;
- c=getchar();
- }
- while(isdigit(c)){
- cnt=cnt*10+c-'0';
- c=getchar();
- }
- return cnt*f;
- }
- int n,t,nxt[M],first[N],to[M],x,match[N],tot,res,ans;
- bool vis[N];
- void add(int x,int y){
- nxt[++tot]=first[x];
- first[x]=tot;
- to[tot]=y;
- }
- int find(int u){
- for(register int i=first[u];i;i=nxt[i]){
- int v=to[i];
- if(vis[v]) continue;
- else {
- vis[v]=true;
- if(match[v]==-1||find(match[v])){
- match[v]=u;
- return 1;
- }
- }
- }
- return 0;
- }
- int hungary(){
- for(register int i=1;i<=n;i++) {
- for(register int j=1;j<=n;j++)vis[j]=false;
- ans+=find(i);
- }
- return ans;
- }
- int main(){
- t=read();
- while(t--) {
- n=read();
- for(register int i=1;i<=n;i++)match[i]=-1;
- for(register int i=1;i<=n;i++)
- for(register int j=1;j<=n;j++) {
- x=read();if(x)add(i,j);
- }
- res=hungary();
- if(res==n)printf("Yes\n");
- else printf("No\n");
- for(register int i=1;i<=n;i++) first[i]=0;
- for(register int i=1;i<=tot;i++) nxt[i]=to[i]=0;
- tot=0;res=0;ans=0;
- }
- return 0;
- }
另外上面代码的初始化非常猥琐......memset 太慢了, 所以自己根据 n 的大小来初始化的不过并没有快多少
来源: http://www.bubuko.com/infodetail-2931893.html