加载中…
个人资料
lovedream
lovedream
  • 博客等级:
  • 博客积分:0
  • 博客访问:59,807
  • 关注人气:40
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

ZOJ3548——大连赛J题二分匹配

(2011-10-06 18:54:12)
标签:

杂谈

分类: 图论

啊!首先赞一下万能的ZOJ!万能的编译器!竟然会自动优化,把我代码给删掉,害我活活卡了十几小时……

题意是给出一个M*N的01点阵,0表示黑,1表示白,要求在里面画出m*n个方阵,使得方阵之间的间隙和点阵边缘都相等,且小于等于方阵的边长。方阵里面的点全部染成白色,其他都黑色。每次染色需时间T,每次可以染一个矩阵,而且任意一个点染过白色就不能再染黑色,染过黑色不能染白色。给出M,N,m,n,T,还有点阵的初始颜色,要求最短时间内得到一张合法的图,求这个时间。

首先设小方阵的边长是k2,间隙是k1.则分两种情况

1.n!=m。则有方程(N-k2*n)/(n+1)==(M-k2*m)/(m+1),解得k2=((m+1)*N-(n+1)*M)/(n-m)。验证这个解即可。

2.n==m,容易得到N==M,否则无解。此时退化到多组解,需要枚举。

得到解后,即得到了目标图,求每个解所需的最小染色次数,取最小就是答案。

那么对于每个解,怎么得到答案呢?

显然如果某个方阵内有黑色点,必然需要对该方阵染一次色,这个直接枚举判断。

对于那些间隙,显然对于某行含有白色点的间隙,直接整行染色肯定不会亏滴,列也是一样。我们要做的,就是计算最少要染多少次行和列。有没有发现已经很接近二分匹配了…(这里的“行”和“列”指的是一整条间隙,不是原图的一行)

如果某些点,不可能被列染色(竖着整列一起染色),即它上下是方阵,而不是行间隙和列间隙的相交位置,则它只能被行染色。这样,该行必须被染色。反之同理。

剩下有些行和列,只在交汇处有白色点,要求这些行和列的最小染色次数。

将有公共白色点的行和列连边,很容易转化为二分图最大点覆盖==二分图最大匹配。

接下来的,就是匹配了……需要注意的是,对每组解,如果都重新扫描点阵以得到匹配信息的话会TLE,需要用子阵和优化。

附一坨代码:

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
const int INF=2100000000;

int sum[2020][2020],match[210],r,c,cntr[210],cntc[210];
char s[2020][2020];
bool vis[210],map[210][210];

bool dfs(int n)         //匹配
{
    int t,i;

    for(i=0;i<=c;i++)if(!vis[i]&&map[n][i])
    {
        vis[i]=1;
        t=match[i];
        match[i]=n;

        if(!(t+1)||dfs(t))
            return 1;
        match[i]=t;
    }
    return 0;
}

bool judge1(int N,int k2,int n)  //判断解是否合法
{
    int t=N-k2*n;
    if(t<=0||t%(n+1))
        return 0;
    t/=n+1;
    if(t>k2)
        return 0;
    return 1;
}
vector<int>V;

int main()
{
    int t,R,C,i,j,k1,k2,k,ans,ans1;

    while(scanf("%d%d%d%d%d",&R,&C,&r,&c,&t)!=EOF)
    {
        for(i=0;i<R;i++)
            scanf("%s",s[i]);
        V.clear();ans=INF;
        memset(map,0,sizeof(map));

        if(r==c)             //解该方程
        {
            if(R==C)
            {
                for(i=1;i*r<R;i++)if(judge1(R,i,r))
                    V.push_back(i);
            }
            else
            {
                printf("-1\n");
                continue;
            }
        }
        else
        {
            k2=(((c+1)*R-(r+1)*C)/(r-c));

            if(k2<=0)
            {
                printf("-1\n");
                continue;
            }
            k1=(R-k2*r)/(r+1);

            if(k1<=0||k1>k2||k2*r+k1*(r+1)-R||k2*c+k1*(c+1)-C)
            {
                printf("-1\n");
                continue;
            }
            V.push_back(k2);
        }

        for(i=1;i<=R;i++)             //子阵和优化
        {
            memset(sum[i],0,sizeof(int)*(C+1));
            for(j=1,k=0;j<=C;j++)
            {
                k+=s[i-1][j-1]-'0';
                sum[i][j]=sum[i-1][j]+k;
            }
        }

        for(int ii=0;ii<V.size();ii++)       //枚举解
        {
            memset(cntr,0,sizeof(cntr));
            memset(cntc,0,sizeof(cntc));
            memset(match,-1,sizeof(match));
            memset(map,0,sizeof(map));

            ans1=0,k2=V[ii],k1=(R-k2*r)/(r+1),k=k1+k2;

            for(i=1;i<=r;i++)         //枚举需要染色的方块
                for(j=1;j<=c;j++)if(sum[i*k][j*k]-sum[i*k-k2][j*k]-sum[i*k][j*k-k2]+sum[i*k-k2][j*k-k2]-k2*k2)
                    ans1++;

            for(i=0;i<=r;i++)
                for(j=0;j<=c;j++)     //枚举间隙相交的黑色方块,cntr和cntc记录的是某行和某列上,仅位于相交黑色方块上得白色点的个数,若等于该行或列上所有白色点的个数,则改行不必一定染色
                {
                    int tt=sum[i*k+k1][j*k+k1]-sum[i*k][j*k+k1]-sum[i*k+k1][j*k]+sum[i*k][j*k];
                    cntr[i]+=tt;
                    cntc[j]+=tt;
                };
            for(i=0;i<=r;i++)
                for(j=0;j<=c;j++)
                {
                    int tt=sum[i*k+k1][j*k+k1]-sum[i*k][j*k+k1]-sum[i*k+k1][j*k]+sum[i*k][j*k];

                    if(!tt)
                        continue;
                    if(cntr[i]-sum[i*k+k1][C]+sum[i*k][C]||cntc[j]-sum[R][j*k+k1]+sum[R][j*k])
                        continue;
                    map[i][j]=1;
                };
            for(i=0;i<=r;i++)if(cntr[i]-sum[i*k+k1][C]+sum[i*k][C])  //枚举一定要染色的行和列
                ans1++;
            for(j=0;j<=c;j++)if(cntc[j]-sum[R][j*k+k1]+sum[R][j*k])
                ans1++;

            for(i=0;i<=r;i++)
            {
                memset(vis,0,sizeof(vis));
                if(dfs(i))
                    ans1++;
            }
            if(ans>ans1)
                ans=ans1;
        }
        printf("%d\n",t*ans);
    }
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有