题解 P6234 【[eJOI2019]T形覆盖】

· · 题解

问题转化

可以将问题转化为：

给定k个十形板的中心，要将每个十形板删掉一个角，使所有十形板不重叠，并且覆盖的数字之和尽可能大。（十形板如下图）

有解性判定

先考虑如何判断有解性。

将每个十形板看做一个点，两个十形板相交的地方看做边，如下图。

当一块板和另一块板相交的地方在它们中心时，由于中心是不能被删除的，所以两个点各连一条自环（一块板的一个角在地图外时同理）。

当两块以上的板相交在同一个点时，连成环是错误的，因为一个格子只能看做一条边。

现在问题变成：能否找到一种方案，使每条边匹配到一个点（一个点不能匹配两条边，但可以匹配0条边）。

一个结论：对于每个连通块，当且仅当它是一棵树或一棵基环树时有解。（手模会发现显然）

求最优解

接下来求最优解就很简单了。

当一个连通块是基环树时，每块板都已经被删去一个角，直接每个被覆盖的格子统计一遍就行。

当一个连通块是树时，有一块板还没有删角，因此执行完基环树的步骤后找出其中一个被覆盖的不是特殊格子的权值最小的格子删去即可。

最后所有连通块答案的和即为最终结果。时间复杂度O(n)

代码

//马蜂比较丑，建议把重点放在注释上 
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>ma[1000010],maa[1000010];
//由于n和m的范围是不确定的，所以要用vector（map会T飞） 
int d[1000010],tail=1,K,jg,ts[1000010][2];
int qwq[1000010];//用于存储每个格子周围的最小值 
bool vv[1000010];
int xx[4]={1,0,-1,0},yy[4]={0,1,0,-1};
struct bbbb{
    int ne,to;
    bool vis;
}b[8000010];
void jb(int x,int y){
    tail++;
    b[tail].ne=d[x];
    b[tail].to=y;
    b[tail].vis=0;
    d[x]=tail;
    return;
}
queue<int>q;
int bfs(int x){//遍历连通块，数点数和边数 
    int cnt=1,cnt1=0,minn=qwq[x];//cnt1：边数  cnt：点数 
    vv[x]=1;
    q.push(x);
    while(q.empty()==false){
        int xxx=q.front();q.pop();
        for(int i=d[xxx];i;i=b[i].ne){
            int y=b[i].to;
            if(b[i].vis==1)continue;
            cnt1++;b[i].vis=b[i^1].vis=1;
            if(vv[y]==1)continue;
            vv[y]=1;cnt++;
            q.push(y);minn=min(minn,qwq[y]);
        }
    }
    if(cnt<cnt1)return -1;
    if(cnt==cnt1)return 0;
    return minn;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){//输入地图 
        ma[i].push_back(0);
        maa[i].push_back(0);
        for(int j=1;j<=m;j++){
            int x;
            scanf("%d",&x);
            ma[i].push_back(x);
            maa[i].push_back(0);
        }
    }
    scanf("%d",&K);
    for(int i=1;i<=K;i++){
        scanf("%d%d",&ts[i][0],&ts[i][1]);
        ts[i][0]++;ts[i][1]++;
        maa[ts[i][0]][ts[i][1]]=-i;//标记每个块的中心点 
    }
    for(int i=1;i<=K;i++){
        qwq[i]=1e9;
        jg+=ma[ts[i][0]][ts[i][1]];     
        for(int j=0;j<4;j++){
            int x=ts[i][0]+xx[j],y=ts[i][1]+yy[j];
            if(x<=0||x>n||y<=0||y>m||maa[x][y]<0){//在地图外或其它块的中心 
                jb(i,i);jb(i,i);//连自环 
            }
            else{
                if(maa[x][y]>0){//角相交 
                    jb(i,maa[x][y]);
                    jb(maa[x][y],i);
                }
                else{
                    jg+=ma[x][y];
                    qwq[i]=min(qwq[i],ma[x][y]);
                }
                maa[x][y]=i;
            }
        }
    }
    int flag=0;
    for(int i=1;i<=K;i++){
        if(vv[i]==0){
            int qaqa=bfs(i);
            if(qaqa==-1){
                flag=1;
                break;
            }
            jg-=qaqa;
        }       
    }
    if(flag==1){
        puts("No");
        return 0;
    }
    cout<<jg;
    return 0;       
}

完结撒花~

p.s.不知道为什么窝的代码跑得那么慢，难道是没写快读（？）

如果有哪里没说清楚的可以随时找窝提问、提建议w~