算法

dinic最大流+tarjan判断强连通分量

时间复杂度

$O(n^2*52^{1/2})$

思路

有个屁思路
很明显的求最大匹配中的必须边,最大匹配只需要用dinic模板
必须边的话我们需要用tarjan判断强连通分量
然后根据性质去判断每一条边就好了
如果(y,x)有值,并且x与y不属于一个强连通分量则此条边为必须边
如果(y,x)有值,或x与y属于一个强连通分量则此条边为可行边 这一条用于 AcWing.380 (同样的做法,只不过求的是可行边)
代码交完没有再修很难看

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define N 100010
int n,m,s,t,p,ans,T;
int head[N],nex[N],e[N],w[N],tot,maxflow,flow;
int d[N],now[N],sum;
vector<int>vec[N];
int num,top,sta[N],v[N],c[N],dfn[N],low[N],cnt;
struct node{
    int xmin,xmax,ymin,ymax;
}a[30];
struct tre{
    int x,y;
}b[30];
struct answer{
    char x;int y;
    bool operator < (const answer &a)const{
        return x<a.x;
}}endd[30];
void add(int x,int y,int z){
    e[++tot]=y,w[tot]=z,nex[tot]=head[x],head[x]=tot;
    e[++tot]=x,w[tot]=0,nex[tot]=head[y],head[y]=tot;
}

bool bfs(){
    memset(d,0,sizeof d);
    queue<int>q;
    q.push(s);d[s]=1;now[s]=head[s];
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nex[i]){
            if(w[i]&&!d[e[i]]){
                q.push(e[i]);
                now[e[i]]=head[e[i]];
                d[e[i]]=d[x]+1;
                if(e[i]==t) return 1;
            }
        }
    }
    return 0;
}

int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow,k,i;
    for(int i=now[x];i&&rest;i=nex[i]){
        if(w[i]&&d[e[i]]==d[x]+1){
            k=dinic(e[i],min(rest,w[i]));
            if(!k) d[e[i]]=0;
            w[i]-=k;
            w[i^1]+=k;
            rest-=k;
        }
    }
    now[x]=i;
    return flow-rest;
}

void add2(int x,int y){
    vec[x].push_back(y);
}

void tarjan(int x){
    dfn[x]=low[x]=++num;
    sta[++top]=x,v[x]=1;
    for(int i=0;i<vec[x].size();i++){
        int y=vec[x][i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y])
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        int y;
        cnt++;
        do{
            y=sta[top--],v[y]=0;
            c[y]=cnt;
        }while(x!=y);
    }
}


int main()
{
    while(cin>>n,n) {
        T++;
        s = 0, t = n + 1, tot = 1, ans = 0,num=0,cnt=0,top=0;
        sum=0x3f3f3f3f;
        memset(head,0,sizeof head);
        for (int i = 1; i <= n; i++) add(s, i + 64, 1);
        for (int i = 1; i <= n; i++) add(i, t, 1);
        for (int i = 1; i <= n; i++)
            cin >> a[i].xmin >> a[i].xmax >> a[i].ymin >> a[i].ymax;
        for (int i = 1; i <= n; i++) {
            cin >> b[i].x >> b[i].y;
            for (int j = 1; j <= n; j++) {
                if (a[j].xmin < b[i].x && a[j].xmax > b[i].x && a[j].ymin < b[i].y && a[j].ymax > b[i].y)
                    add(j + 64, i, 1), sum = min(sum, tot);
            }
        }
        int flow = 0;
        while (bfs())
            while (flow = dinic(s, 0x3f3f3f3f)) maxflow += flow;
        //
        memset(v,0,sizeof v);
        memset(dfn,0,sizeof dfn);
        memset(low,0,sizeof low);
        for(int i=0;i<100;i++)
            vec[i].clear();
        for (int i = 2; i <= tot; i += 2) {
            if (!w[i]) add2(e[i], e[i ^ 1]);
            else add2(e[i ^ 1], e[i]);
        }
        for (int i = s; i <= 64 + n; i++) {
            if (!dfn[i]) tarjan(i);
            if (i == t) i = 64;
        }
        for (int i = sum; i <= tot; i += 2)
            if (w[i] && c[e[i ^ 1]] != c[e[i]]){
                endd[ans].x=e[i],endd[ans++].y=e[i^1];
            }
        cout<<"Heap "<<T<<endl;
        if(ans==0){
            cout<<"none"<<endl;
        }
        else {
            sort(endd, endd + ans);
            for (int i = 0; i < ans; i++)
                printf("(%c,%d) ", endd[i].x, endd[i].y);
            cout <<endl;
        }
        cout<<endl;
    }
    return 0;
}