算法1

(dinic + tarjan求强连通分量)

二分图左部为幻灯片右部为数字，若幻灯片覆盖数字则从该幻灯片向覆盖数字连边；
二分图最大匹配中的必须边即为幻灯片的编号
在二分图中，必须边的判定条件为：(x,y)的流量为1(残留网络中无流量)，并且在残留网络中xy属于不同的强连通分量；
PS：可行边的判定条件为：(x,y)的流量为1(残留网络中无流量)或者在残留网络中xy属于同一个强连通分量；

C++ 代码

const int N = 3e5+5,M = N * 2;
int mod = 1e9 +7;
int n,m,k,S,T;
struct node{
    int l,r,d,u;
}a[N];
bool cover(node a,int x,int y){
    int l = a.l,r = a.r,d = a.d,u = a.u;
    return x >= l && x <= r && y >= d && y <= u;
}
int e[M],ne[M],f[M],h[N],idx;
void add(int a,int b,int c){
    e[idx] = b,f[idx] = c,ne[idx] = h[a],h[a] = idx++;
    e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx++;
}
int d[N],cur[N];
bool bfs(){
    queue<int> q;
    q.push(S);
    memset(d,0,sizeof(d));
    d[S] = 1,cur[S] = h[S];
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i = h[u] ; ~i ; i = ne[i]){
            int ver = e[i];
            if(!d[ver] && f[i]){
                d[ver] = d[u] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                q.push(ver); 
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u] ; ~i && flow < limit ; i = ne[i]){
        int ver = e[i];
        cur[u] = i;
        if(d[ver] == d[u] + 1 && f[i]){
            int k = find(ver,min(f[i],limit - flow));
            if(!k) d[ver] = 0;
            f[i] -= k,f[i ^ 1] += k,flow += k;
        }
    }
    return flow;
} 
int dinic(){
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r += flow;
    return r;
}
int dfn[N],stk[N],id[N],low[N],scc_cnt,top,ts;
bool instk[N];
void tarjan(int u){
    dfn[u] = low[u] = ++ts;
    stk[++top] = u,instk[u] = true;
    for(int i = h[u] ; ~i ; i = ne[i]){
        int v = e[i];
        if(f[i]){
            if(!dfn[v]){
                tarjan(v);
                low[u] = min(low[u],low[v]);
            }
            else if(instk[v]) low[u] = min(low[u],dfn[v]);
        }

    }
    if(dfn[u] == low[u]){
        int y;
        scc_cnt++;
        do{
            y = stk[top--];
            instk[y] = false;
            id[y] = scc_cnt;
        }while(y != u);
    }
}
int ans[N];
void solve(){
    S = 0,T = 2 * n + 1;
    memset(h,-1,sizeof(h));
    idx = 0;
    for(int i = 1 ; i <= n ; ++i){
        int u,d,l,r;
        cin >> l >> r >> d >> u;
        a[i] = {l,r,d,u};
        //源点向幻灯片连边
        add(S,i,1);
    }
    for(int i = 1 ; i <= n ; ++i){
        int x,y;
        cin >> x >> y;
        //数字向汇点连边
        add(i + n,T,1);
        for(int j = 1 ; j <= n ; ++j){
            //若幻灯片j能覆盖数字i则连边
            if(cover(a[j],x,y)) add(j,i + n,1);
        }
    }
    dinic();
    memset(dfn,0,sizeof(dfn));
    top = scc_cnt = ts = 0;
    for(int i = S; i <= T ; ++i){
        if(!dfn[i]) tarjan(i);
    }
    memset(ans,0,sizeof(ans));
    int cnt = 0;
    for(int i = 0 ; i < idx ; i += 2){
        int a = e[i ^ 1],b = e[i];
        if(a == S || a == T || b == S || b == T) continue;
        //若ab之间有流量即残留网络中无流量，且残留网络中不在同一个强连通分量中
        if(!f[i] && id[a] != id[b] ) ans[a] = b - n,cnt++;
    }
    static int tt = 1;
    printf("Heap %d\n",tt++);
    if(cnt == 0) puts("none");
    else{
        for(int i = 1 ; i <= n ; ++i){
            if(ans[i]) printf("(%c,%d) ",i - 1 + 'A',ans[i]);
        }   
        puts("");
    }
    puts("");
}

signed main(){
    while(cin >> n,n)
    solve();
    return 0;
}