文章目錄

• 題目描述
• • 數據范圍
• 解析
• 解析

題目描述

有一堆透明的幻燈片堆疊在一起，每個幻燈片上的隨機一個位置會有幻燈片的標號。
因為幻燈片是透明的，所以堆疊在一起的幻燈片使得這些標號分不清各自對應的幻燈片。
現在要求你求出那些能夠確定對應關系的幻燈片以及對應的標號。

數據范圍

$n<=26$

解析

面對這樣的數據范圍，我還是不夠暴力…
關鍵的思路就是暴力枚舉每一條邊，判斷刪掉這條邊之后是否仍是完美匹配

解析

#include<bits/stdc++.h> using namespace std; const int N=65; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; } int n,m; struct node{int from,to,nxt; }p[N*N*2]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){x,y,fi[x]};fi[x]=cnt; } int a[N],b[N],c[N],d[N],x[N],y[N]; bool in(int x,int y,int i){//printf("x=%d y=%d i=%d %d %d %d %d\n",x,y,i,a[i],b[i],c[i],d[i]);//printf(" %d %d %d %d\n",x>=a[i],x<=b[i],y>=c[i],y<=d[i]);return x>=a[i]&&x<=b[i]&&y>=c[i]&&y<=d[i]; } int E; int vis[N],mat[N],num,ans[N]; bool dfs(int x,int tim){if(vis[x]==tim) return false;vis[x]=tim;for(int i=fi[x];~i;i=p[i].nxt){if(i==E) continue;int to=p[i].to;if(!mat[to]||dfs(mat[to],tim)){mat[to]=x;return true;}}return false; } int hangary(){int res=0;memset(vis,0,sizeof(vis));memset(mat,0,sizeof(vis));for(int i=1;i<=n;i++){if(dfs(i,i)) res++;}return res; } int main(){int o=0;while(scanf("%d",&n)!=EOF){if(!n) break;memset(fi,-1,sizeof(fi));cnt=-1;num=0;memset(ans,0,sizeof(ans));for(int i=1;i<=n;i++){a[i]=read();b[i]=read();c[i]=read();d[i]=read();}for(int i=1;i<=n;i++){x[i]=read();y[i]=read();for(int j=1;j<=n;j++){if(in(x[i],y[i],j)){addline(j,i+n);}}}for(int i=0;i<=cnt;i++){E=i;if(hangary()!=n){num++;ans[p[i].from]=p[i].to-n;}}printf("Heap %d\n",++o);if(!num) printf("none\n");else{for(int i=1;i<=n;i++){if(ans[i]) printf("(%c,%d) ",'A'+i-1,ans[i]);}printf("\n");}printf("\n");}return 0; } /* */

總結

以上是生活随笔為你收集整理的YBTOJ：幻灯片（二分图匹配）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。