传送门
题意：有一些1*2的骨牌在方格中，每个骨牌要么平行于X轴，要么平行于Y轴。同方向的骨牌不会相互覆盖。你的任务是移走一些骨牌，使得剩下的骨牌不会相互覆盖，且数量最多。
//HDU 4619 建边+匈牙利 struct Edge{ int to,next; }edge[maxn]; int tot,head[maxn]; int n,m; void add_edge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } pair<int,int>p2[maxn]; pair<int,int>p1[maxn]; bool vis[maxn]; int nxt[maxn]; bool find(int u){ for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(!vis[v]){ vis[v]=true; if(nxt[v]==0||find(nxt[v])){ nxt[v]=u; return true; } } } return false; } // 第二次看是真的理解了吧 // 移去部分骨牌，使留下不会相互覆盖的骨牌数量最多(同方向骨牌不会相互覆盖) // 分析：ans=n+m-不同方向的最大匹配数 int match(){ int ans=0; for(int i=1;i<=n;i++){ memset(vis,false,sizeof(vis)); if(find(i)) ans++; } return ans; } int main() { while (~scanf("%d%d",&n,&m)&&n&&m){ memset(head,-1,sizeof(head)); memset(nxt,0,sizeof(nxt)); for(int i=1,x,y;i<=n;i++) cin>>x>>y,p1[i]=make_pair(x,y); for(int i=1,x,y;i<=m;i++) cin>>x>>y,p2[i]=make_pair(x,y); /*相互覆盖的部分建边，题目给出：n块 (x1,y1)(x1+1,y1)规格的的骨牌 m块(x2,y2)(x2,y2+1) 规格的骨牌 有四种覆盖的情况：(x1,y1)与(x2,y2),(x1,y1)与(x2,y2+1) (x1+1,y1)与(x2,y2),(x1+1,y1)与(x2,y2+1)*/ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int a=p1[i].first,b=p1[i].second; int c=p2[j].first,d=p2[j].second; if((a==c&&b==d)||(a==c&&b==d+1)||(b==d&&c==a+1)||(c==a+1&&b==d+1)) add_edge(i,j); } printf("%d\n",n+m-match()); } return 0; }