P1283 平板涂色

题目传送门

一看数据，是可以爆搜的。

思路

我们看，当要涂一个矩形的时候，他上面的矩形就都要涂掉
于是我们就可以自然而然的想到拓扑
或者说我们把整个平板抽象成一个有向图，每个矩形就是一个点，他的限制就是边

比如样例：

就可以抽象成

建图就可以暴力建，才100*100的数据

然后就在图上 dfs， 枚举颜色，用拓扑去尽量涂掉这个颜色的矩形

小剪枝：记录一个rest_col，为未涂完的颜色数量。如果当前答案加rest_col大于等于最优答案，必定不行，回溯。

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define y1 yy1
#define pc putchar
using namespace std;
template<typename T>
inline void read(T &x)
{
    x=0;
    T f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)){x=x*10+(c^48); c=getchar();}
    x*=f;
    return;
}
template<typename T,typename... Args> inline void read(T &x, Args&... args){read(x); read(args...);}
template<typename Z>
inline void write(Z x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
template<typename Z,typename... Args> inline void write(Z x, Args... args){write(x); putchar(' '); write(args...);}
const int COL=20+5, BLO=16+5;
const int N=10000+5;
vector<int> e[N];
void add(int x,int y){e[x].push_back(y);}
int rest_col;//还有几种颜色没涂
int block[COL][BLO];//矩形的编号，第一维是颜色，第二维是编号
int cnt_block[COL];//这个颜色的矩形有多少个
int mp[100][100];//暴力建图
int ind[BLO];//每个矩形的入度
bool paint[BLO];//这个矩形是否已经被删除了
int col[BLO];//这个矩形的颜色是什么
int rest_block[COL];//这种颜色还剩下几个矩形没有涂
int ans=0x7fffffff;
void dfs(int pos)
{
    if(pos + rest_col >= ans) return;//剪枝，当前答案大于等于最优答案，必定不行
    if(rest_col == 0)//全都涂完了
    {
	ans = pos;
	return;
    }
    int cnt=0;
    for(int c=1; c<=20 && cnt < rest_col; c++)//枚举每种颜色
    {
	if(cnt_block[c] == 0 || rest_block[c] == 0) continue;//这个颜色的矩形没有或者涂完了
	bool can_paint = 0;//有没有能涂的
	queue<int> pain/*可以涂的矩形的队列*/, del/*涂掉的矩形的队列*/, ind_upd/*更改过入度的矩形的队列*/;
	for(int i=1;i<=cnt_block[c];i++)
	    if(!paint[block[c][i]] && ind[block[c][i]] == 0)//没被涂上色，没有入度，可以直接涂
	    {
		can_paint = 1;
		pain.push(block[c][i]);
	    }
	if(can_paint) cnt++;
	else continue;//这种色涂不上任何一个矩形
	while(!pain.empty())//拓扑
	{
            int x = pain.front();
	    pain.pop();
	    paint[x] = 1;
	    del.push(x);
	    rest_block[c]--;
	    for(auto t:e[x])
	    {
		ind[t]--;
		ind_upd.push(t);
		if(ind[t] == 0 && col[t] == c)//没有入度，颜色一样（不用换刷子
                    pain.push(t);
	    }
	}
	if(rest_block[c] == 0) rest_col--;//这种色的矩形全涂完了
	dfs(pos + 1);
	if(rest_block[c] == 0) rest_col++;//回溯
	while(!del.empty())
	{
	    paint[del.front()] = 0;
	    rest_block[c]++;
	    del.pop();
	}
	while(!ind_upd.empty())
	{
	    ind[ind_upd.front()]++;
	    ind_upd.pop();
	}
    }
}

int n,x1,y1,x2,y2,c;
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
    {
	read(x1, y1, x2, y2, c);		
        rest_block[c]++;
	col[i] = c;
	if(cnt_block[c] == 0) rest_col++;
	cnt_block[c]++;
	block[c][cnt_block[c]] = i;
	for(int x=x1;x<=x2;x++)
	    for(int y=y1;y<=y2;y++)
		mp[x][y] = i;
    }
    for(int x=0;x<99;x++)
	for(int y=0;y<=99;y++)
	{
            int pre=0, nxt=0;
            if(mp[x][y] == mp[x+1][y]) continue;//同一个块
            if(!mp[x][y] || !mp[x+1][y]) continue;//不存在
            if(mp[x][y] != pre && mp[x+1][y] != nxt)//防止重复建边
	    {
		pre = mp[x][y];
		nxt = mp[x+1][y];
		add(pre, nxt);
		ind[nxt]++;
            }
	}
    dfs(0);
    write(ans);
    return 0;
}