P2417 课程
裸地匈牙利算法,
贪心的不断匹配,若没匹配,则匹配;反之,判断与之匹配的点能否在找另一个点匹配,若能,抢多这个点与之匹配
时间复杂度$O(n\times m)$
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2000000
using namespace std;struct node{
int to,next;
}e[N];
int t,head[N],tot,p,n,match[N],dfn[N],ans;void add(int u,int v){
e[++tot].to=v,e[tot].next=head[u],head[u]=tot;
}bool dfs(int u,int t){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dfn[v]!=t){
dfn[v]=t;
if(!match[v]||dfs(match[v],t)){
match[v]=u;return true;
}
}
}
return false;
}int main()
{
scanf("%d",&t);
while(t--){
memset(head,,sizeof(head));
memset(match,,sizeof(match));
memset(dfn,,sizeof(dfn));
tot=ans=;
scanf("%d%d",&p,&n);
for(int m,v,i=;i<=p;i++){
scanf("%d",&m);
for(int j=;j<=m;j++){
scanf("%d",&v),add(v,i);
}
}
for(int i=;i<=n;i++)
if(dfs(i,i)) ++ans;
if(ans>=p) printf("YES\n");
else printf("NO\n");
} return ;
}
P2071 座位安排
模板,又是模板,建图方式有一点儿不同,因为每一排有两个座位
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2000000
using namespace std;struct node {
int to,next;
} e[N];
int t,head[N],tot,p,n,match[N],dfn[N],ans;void add(int u,int v) {
e[++tot].to=v,e[tot].next=head[u],head[u]=tot;
}bool dfs(int u,int t) {
for(int i=head[u]; i; i=e[i].next) {
int v=e[i].to;
if(dfn[v]!=t) {
dfn[v]=t;
if(!match[v]||dfs(match[v],t)) {
match[v]=u;
return true;
}
}
}
return false;
}int main() {
memset(head,,sizeof(head));
memset(match,,sizeof(match));
memset(dfn,,sizeof(dfn));
tot=ans=;
scanf("%d",&n);
for(int x,y,i=; i<=n*; i++) {
scanf("%d%d",&x,&y);
add(i,x),add(i,x+n),add(i,y),add(i,y+n);
}
for(int i=; i<=n*; i++)
if(dfs(i,i)) ++ans;
printf("%d\n",ans); return ;
}
P1894 [USACO4.2]完美的牛栏The Perfect Stall
裸题
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2000000
using namespace std;struct node {
int to,next;
} e[N];
int t,head[N],tot,m,n,match[N],dfn[N],ans;void add(int u,int v) {
e[++tot].to=v,e[tot].next=head[u],head[u]=tot;
}bool dfs(int u,int t) {
for(int i=head[u]; i; i=e[i].next) {
int v=e[i].to;
if(dfn[v]!=t) {
dfn[v]=t;
if(!match[v]||dfs(match[v],t)) {
match[v]=u;
return true;
}
}
}
return false;
}int main() {
memset(head,,sizeof(head));
memset(match,,sizeof(match));
memset(dfn,,sizeof(dfn));
tot=ans=;
scanf("%d%d",&n,&m);
for(int v,x,i=; i<=n; i++) {
scanf("%d",&x);
for(int j=;j<=x;j++) {
scanf("%d",&v);
add(i,v);
}
}
for(int i=; i<=n; i++)
if(dfs(i,i)) ++ans;
printf("%d\n",ans); return ;
}