P7450 [THUSCH2017] 巧克力
题意
给定一张网格图，每个格子有两个权重,\((a,c)\)，我们希望找出一个不包含 \(c=-1\) 的联通块并且 \(a\) 的中位数最大，同时还要包含 \(k\) 种颜色。
题解
套路题都是nb题。
首先 \(k\) 比较小，我们可以考虑一个类似斯坦纳树的 \(dp\)。
\(f_{i,j,S}\) 表示以 \((i,j)\) 为 根，满足状态有 \(S\) 的最小联通块大小。
需要注意的是这里是点的贡献不是边的贡献，所以在枚举子集转移的时候要减去当前根的重复贡献。
但是我们并不知道 \(k\) 个颜色是哪 \(k\) 个颜色，考虑随机化将所有颜色重新分配成 \([1,k]\) 种颜色。
若最优解中的 \(k\) 种颜色被赋上的颜色互不相同则就能算出正确答案，容易分析得正确的概率为 \(\frac{k!}{k^k}\)，多随机几百次就可以了。
然后考虑如何和解决中位数，考虑二分，将价值转为 \(-1,1\) 的样子，求和为负数的连通块。
注意到这样不太好满足联通块最小的条件。
有一个很厉害的做法，将 \(-1\) 改为 \(9999\)，\(1\) 改为 \(10001\)，求出来的答案比最小连通块的 \(1000\) 倍小说明合法。
正确性显然，实际上类似于给大小和中位数上一个优先级，在满足大小最小的前提下再令和最小。，可能也有其它做法，但是我觉得这个处理方法还是很妙的。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
bool S_GND ;
const int K = 6 ;
const int N = 240 ;
const int INF = 1e9+7 ;
int n,k,m,T,top ;
int col[N*N],f[N][N][1<<K] ;
int a[N][N],w[N][N],c[N][N],now[N],vis[N][N] ;
int fx[10][10] = {{0,1},{1,0},{-1,0},{0,-1}} ;
mt19937 rd(19260817) ;
void SPFA(int S)
{
queue<pii>q ; //cerr<<"!" ;
FOR(i,1,n,1) FOR(j,1,m,1) if(f[i][j][S] != INF) q.push({i,j}),vis[i][j] = 1 ;
while(!q.empty())
{
auto [x,y] = q.front() ; q.pop(),vis[x][y] = 0 ;
FOR(k,0,3,1)
{
int X = x+fx[k][0],Y = y+fx[k][1] ;
if(X < 1 || Y < 1 || X > n || Y > m || c[X][Y] == -1) continue ; //assert(w[X][Y] > 0) ;
if(f[X][Y][S] > f[x][y][S]+w[X][Y])
{
// print(S,f[x][y][S],f[X][Y][S],w[X][Y]),enter ;
f[X][Y][S] = f[x][y][S]+w[X][Y] ;
if(!vis[X][Y]) q.push({X,Y}),vis[X][Y] = 1 ;
}
}
}
}
int solve()
{
int res = INF ;
FOR(QAQ,1,200,1)
{
shuffle(col+1,col+top,rd) ;
FOR(i,1,n,1) FOR(j,1,m,1) FOR(S,0,(1<<k)-1,1) f[i][j][S] = INF ;
FOR(i,1,top,1) if(~col[i]) now[col[i]] = i%k ;
FOR(i,1,n,1) FOR(j,1,m,1) if(~c[i][j]) f[i][j][1<<now[c[i][j]]] = w[i][j] ;
FOR(S,0,(1<<k)-1,1)
{
for(int T = S&(S-1) ; T ; T = (T-1)&S) FOR(i,1,n,1) FOR(j,1,m,1) if(~c[i][j])
f[i][j][S] = min(f[i][j][S],f[i][j][T]+f[i][j][S^T]-w[i][j]) ; SPFA(S) ;
}
FOR(i,1,n,1) FOR(j,1,m,1) if(~c[i][j]) res = min(res,f[i][j][(1<<k)-1]) ;
}
return res ;
}
void Solve()
{
read(n,m,k),top = 0 ;
FOR(i,1,n,1) FOR(j,1,m,1) read(c[i][j]) ;
FOR(i,1,n,1) FOR(j,1,m,1) read(a[i][j]) ; //cerr<<"!" ;
FOR(i,1,n,1) FOR(j,1,m,1) col[++top] = c[i][j],w[i][j] = 1 ;
sort(col+1,col+1+top),top = unique(col+1,col+1+top)-col-1 ; //cerr<<"!" ;
int sz = solve(),le = 1,ri = 1e6,res = 0 ; //cerr<<"!" ;
if(sz == INF){print(-1,-1),enter ; return ;}
while(le <= ri)
{
int mid = le+ri>>1 ;
FOR(i,1,n,1) FOR(j,1,m,1) w[i][j] = a[i][j]<=mid?9999:10001 ;
int num = solve() ; if(num <= sz*10000) ri = mid-1,res = mid ; else le = mid+1 ;
}
print(sz,res),enter ;
}
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(T) ; while(T--) Solve() ;
return 0 ;
}