Sorting Slides

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 384K, 提交时间: 2022-08-31 21:37:12

#include<bits/stdc++.h>
using namespace std;
int link[30],rlink[30],n;
bool g[30][30],chk[30];
bool findpath(int x)
{
    for(int y=0;y<n;y++)
    {
        if(g[x][y]&&!chk[y])
        {
            chk[y]=true;
            if(rlink[y]==-1||findpath(rlink[y]))
            {
                rlink[y]=x;
                link[x]=y;
                return true;
            }
        }
    }
    return false;
}
int maxmatch()
{
    memset(link,-1,sizeof(link));
    memset(rlink,-1,sizeof(rlink));
    int ret=0;
    for(int x=0;x<n;x++)
    {
        memset(chk,false,sizeof(chk));
        if(findpath(x))
            ret++;
    }
    return ret;
}
struct Rec
{
    int minx,maxx,miny,maxy;
};
Rec rec[30];
int main()
{
    int ca=0;
    while(scanf("%d",&n)&&n)
    {
        if(ca)
            printf("\n");
        memset(g,false,sizeof(g));
        for(int i=0;i<n;i++)
            scanf("%d%d%d%d",&rec[i].minx,&rec[i].maxx,&rec[i].miny,&rec[i].maxy);
        for(int i=0;i<n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            for(int j=0;j<n;j++)
            {
                if(x>=rec[j].minx&&x<=rec[j].maxx&&y>=rec[j].miny&&y<=rec[j].maxy)
                {
                    g[j][i]=true;
                }
            }
        }
        maxmatch();
        printf("Heap %d\n",++ca);
        bool flag=true,ths;
        for(int i=0;i<n;i++)
        {
            int t=link[i],rl;
            ths=true;
            for(int j=0;j<n;j++)
            {
                if(t!=j&&g[i][j])
                {
                    rl=rlink[j];
                    link[rl]=-1;
                    rlink[j]=i;
                    link[i]=j;
                    rlink[t]=-1;
                    memset(chk,false,sizeof(chk));
                    chk[j]=true;
                    if(findpath(rl))
                    {
                        ths=false;
                        break;
                    }
                    rlink[j]=rl;
                    link[rl]=j;
                    link[i]=t;
                    rlink[t]=i;
                }
            }
            if(ths)
            {
                if(!flag)
                    printf(" ");
                flag=false;
                printf("(%c,%d)",'A'+i,link[i]+1);
            }
        }
        if(flag)
            printf("none");
        printf("\n");
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 208K, 提交时间: 2019-11-30 20:01:20

#include<cstdio>
#include<cstring>
using namespace std;
#define N 27
int vis[N],match[N],ans[N],x1[N],x2[N],y1[N],y2[N],n,T;
bool g[N][N],flag;
 
inline bool dfs(int x) {
    for (register int i=1; i<=n; i++)
        if (!vis[i] && g[x][i]) {
            vis[i]=1;
            if (!ans[i] || dfs(ans[i])) {
                ans[i]=x;//第 i 个幻灯片对应数字为 x
                return true;
            }
        }
    return false;
}
 
inline int find() {//求二分图最大匹配
    int sum=0;
    memset(ans,0,sizeof ans);
    for (register int x=1; x<=n; x++){
            memset(vis,0,sizeof vis);
            if (dfs(x)) sum++;// 总匹配数
    }
    return sum;
}
 
int main() {
    while(~scanf("%d",&n) && n) {
        if (T) puts("");
        printf("Heap %d\n",++T);
        memset(g,0,sizeof g);
 
        for (int i=1; i<=n; i++)
            scanf("%d%d%d%d",&x1[i],&x2[i],&y1[i],&y2[i]);
            
        for (int i=1,x,y; i<=n; i++) {
            scanf("%d%d",&x,&y);
            for (int j=1; j<=n; j++)
                if (x>=x1[j] && x<=x2[j] && y>=y1[j] && y<=y2[j])
                    g[i][j]=1;//如果数字在幻灯片范围之内的话则连边，有机会匹配
        }
 
        int tot=find(),flag=0;
        
                //接下来我们要去除这种情况
         
        for (int j=1; j<=n; j++)
            for (int i=1;i<=n; i++)
                if (g[i][j]) {
                    g[i][j]=0;//考虑依次删去每条边，如果有唯一对应，那么至少有一边删去后使匹配数减少
                    if (find()!=tot) {
                        if (flag) printf(" ");
                        else flag=1;
                        printf("(%c,%d)",j-1+'A',i);//如果幻灯片 j 与 数字 i 是唯一搭配，直接输出
                    }
                    g[i][j]=1;
                }
        if (!flag) printf("none");//如果删去任意一边匹配数都不变，则对应不唯一
        puts("");//相当于printf("\n");
    }
    return 0;
}

详情