P3227 [HNOI2013]切糕
题意
给定一个 \(P \times Q\) 的平面，平面上每一个点上都有一个高度为 \(R\) 的竖条。
竖条上每一个点都有一个不和谐度 \(f(x,y,z)\) ，对于每一个竖条选一个点，要求与周围的点的高度差不超过 \(d\) (四联通)，求最小不和谐度。
题解
感觉这道题很神啊，首先我们考虑没有 \(d\) 的限制的做法。
这样每一个竖条都成为了独立的问题，我们可以想到对每一个竖条找到最小值。
然后我们可以联想到最小割，想一种等价的连边方式，设点 \(g_{i,j,k}\) 表示在平面 \((i,j)\) 的竖条上高度为 \(k\) 的点。
1.\(s\) 向 \(g_{i,j,1}\) 连一条流 \(INF\) 的边。
2.\(g_{i,j,k}\) 向 \(g_{i,j,k+1}\) 连接一条流 \(f(i,j,k)\) 的边。
3.\(g_{i,j,R}\) 向 \(t\) 连一条流 \(f(i,j,R)\) 的边。
我们会发现我们组成了 \(P \times Q\) 的链，显然割一条边链就不连通了，是这条链上权值最小的那一条边。
接下来我们考虑加上 \(d\) 的限制，接下来连边的操作就很神了，设 \(g_{i',j'}\) 是 \(g_{i,j}\) 在平面上相邻的链。
我们由 \(g_{i,j,k}\) 向 \(g_{i',j',k-d}\) 连一条流 \(INF\) 的边，这条边保证了我们只能割掉链 \(g(i',j')\) 大于 \(k-d\) 的边。
由于 \(g_{i,j,k}\) 也会受到来自 \(g_{i',j',k+d}\) 的连边，若是割掉了 \(g_{i',j'}\) 中大于 \(k+d\) 的边，则 \(g_{i,j,k}\) 也无法被选择，所以这就保证了 \(g_{i',j'}\) 中只有 \([k-d,k+d]\) 之间的边会被割掉。
同理如果是向 \(g_{i',j',k+d}\) 连边的话，其实也相同，只能割掉大于 \(k+d\) 的边，只是这样控制区间就不太方便了。
code
/*狮忆是第一个被抓的，当时狮忆接到通知要去吃早茶，他兴冲冲的刚下车时，他的随身背包即被留在爹妈身上。狮忆感到事情有些不大对头，但也没在意。当狮忆快走进大门时，专门对付他的创伤小组立即走了过来。创伤小组几个护士在走廊里把他扭住的时候，狮忆惊慌失措，一边大声说 “我是来吃早茶的，你们要干什么？”一边拳打脚踢，拼命进行反抗。创伤小组的护士个个身手不凡，狮忆很快就被创伤小组制服了，被扭着双臂押到了精神病院里。在精神病院里，等待他的神经科主任把“治疗决定”念了一遍。还没等主任念完，狮忆突然大吼一声，挣脱护士的扭缚，向五六米远地方的母亲猛扑过去。狮忆年纪轻轻，去过健身房，一旦扑过去，打伤了他妈妈，这还了得？他妈妈久经沙场，不慌不忙的冷眼看着狮忆的疯狂举动。在这千钧一发之际，一旁的护士反应迅速，猛冲上去把狮忆的病房大门关上，死死地把他摁住，夺走了他的手机。在今天的精神病院入住的成员中，狮忆是唯一被束缚在控制床的人。狮忆住院后，对他的监管也最严格的。*/
#include <bits/stdc++.h>
#define int long long
#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 ;
const int N = 105 ;
const int M = 5000005 ;
const int INF = 1e18 ;
int n,m,p,d,s,t,cnt = 1,ans,top ;
int gen[N][N][N],id[N][N][N] ;
int dep[N*N*N],vis[N*N*N],fx[5][5] = {{1,0},{0,1},{-1,0},{0,-1}} ;
struct Edge{int v,w ;}E[2*M] ;
vector<int>e[N*N*N] ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int fk(0) ; rg char c(gc()) ;
while(!isdigit(c)) fk |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (fk?-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...) ;
}
inline void Add(int u,int v,int w)
{
// print(u,v,w),enter ;
E[++cnt] = {v,w},e[u].pb(cnt) ;
E[++cnt] = {u,0},e[v].pb(cnt) ;
}
inline int Bfs()
{
me(dep,0x3f),me(vis,0),dep[s] = 0 ;
queue<int>q ; q.push(s) ;
while(!q.empty())
{
int x = q.front() ; q.pop() ;
for(auto id:e[x])
{
int v = E[id].v,w = E[id].w ;
if(!w || dep[x]+1 >= dep[v]) continue ;
dep[v] = dep[x]+1 ;
if(v == t)return 1 ;
if(!vis[v]) q.push(v),vis[v] = 1 ;
}
}
if(dep[t] == dep[0]) return 0 ;
return 1 ;
}
int Dfs(int x,int flow)
{
if(x == t) return flow ;
int us = 0 ;
for(auto id:e[x])
{
int v = E[id].v,w = E[id].w ;
if(!w || dep[x]+1 != dep[v]) continue ;
int low = Dfs(v,min(w,flow-us)) ;
if(low) us += low,E[id].w -= low,E[id^1].w += low ;
if(us == flow) break ;
}
if(!us) dep[x] = 0 ;
return us ;
}
signed main()
{
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n,m,p,d),s = n*m*p+100,t = s+1 ;
FOR(l,1,p,1) FOR(i,1,n,1) FOR(j,1,m,1) read(gen[i][j][l]) ;
FOR(i,1,n,1) FOR(j,1,m,1) FOR(l,1,p,1) id[i][j][l] = ++top ;
FOR(i,1,n,1) FOR(j,1,m,1) FOR(l,1,p,1) FOR(r,0,3,1)
{
int X = i+fx[r][0],Y = j+fx[r][1] ;
if(X > n || X < 1 || Y > m || Y < 1) continue ;
if(l-d > 0) Add(id[i][j][l],id[X][Y][l-d],INF) ;
}
FOR(i,1,n,1) FOR(j,1,m,1) Add(s,id[i][j][1],INF),Add(id[i][j][p],t,gen[i][j][p]) ;
FOR(i,1,n,1) FOR(j,1,m,1) FOR(l,1,p-1,1) Add(id[i][j][l],id[i][j][l+1],gen[i][j][l]) ;
while(Bfs())
{
int rp = Dfs(s,INF) ;// cerr<<"!" ;
ans += rp ; assert(rp >= 0) ;
}
print(ans) ;
return 0 ;
}
...
总结一下。
这道题最妙的地方就是用流无限的边来控制图的连通性，其实更进一步的是确定割边的范围，所以有关区间的最小割题目，我们可以尝试采用类似的方法。