Reincarnation

正因为梦易碎，才格外美好。

号家军集训 网络流选做

发表于 更新于 分类于
本文字数： 9.7k 阅读时长 ≈ 9 分钟

讲师：丁晓漫

连模板都不会打了。

切糕

题目简介

题目名称：切糕
题目来源：湖南省选 （存疑）

评测链接 ：https://loj.ac/p/2384
评测链接 ：https://www.luogu.com.cn/problem/P3227

形式化题意：在三维平面中存在一个 的立方体包含 ，每个点有一个权值 ，则这个立方体存在 条高度为 的竖线，你需要在这 条竖线上取一个点 并得到该点的权值，并保证对于所有 有 ，求最小权值。

数据范围：

考虑网络流的形式，显然在没有 的限制下我们取 就可以了，这样的话，我们用 条路径把竖线连起来，建边 流量 ，再建边 流量 就行了。并让 与所有的 相连流量 ，此时的最大流就是最小权值。

然后考虑 的限制，我们把问题转化到从原题意开始思考，转化为最小割，也就是花费最少的代价让 割开，而问题就在于，对于相邻的两条竖线割的地点不能超过 ，所以我们需要另添一些路径让超过 的地方不能被割开。换个角度说，就是让如果割开地点超过了 ，我们有另一条路径使 连通。

所以考虑连接所有 ，而这条边是不允许被割开的，所以流量 。

然后求出最小割，也就是跑最大流就可以了。注意三维面转化成序列的时候一定要算清楚（或者开个 记一下）。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
// ----- Eternally question-----
// Problem: P3227 [HNOI2013] 切糕
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3227
// Memory Limit:  125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-17 09:22:03
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=50,MAXS=5e5+10,MAXM=2e6+10;
const int INF=0x3f3f3f3f;
const int dx[]={0,1,-1,0,0};
const int dy[]={0,0,0,1,-1};
int P,Q,R,D,S,T;
struct Netflow
{
	int next,to,val;
	Netflow(int n=0,int t=0,int v=0):next(n),to(t),val(v){}
}Edge[MAXM<<1];
int Head[MAXS],Cur[MAXS],Total=1;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=Netflow(Head[u],v,w);Head[u]=Total;
	Edge[++Total]=Netflow(Head[v],u,0);Head[v]=Total;
}
int Fl[MAXS];
inline bool Bfs()
{
	std::queue<int>Q;
	std::memset(Fl,-1,sizeof(Fl)),Fl[S]=1;
	Q.push(S),Cur[S]=Head[S];
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(Edge[e].val&&Fl[v]==-1)
			{
				Fl[v]=Fl[u]+1,Cur[v]=Head[v];
				if(v==T) return 1;
				Q.push(v);
			}
		}
	}
	return 0;
}
int Dfs(int x,int inf)
{
	if(x==T) return inf;
	int flow=0;
	for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
	{
		v=Edge[e].to,Cur[x]=e;
		if(Edge[e].val&&Fl[v]==Fl[x]+1)
		{
			int k=Dfs(v,std::min(Edge[e].val,inf-flow));
			if(!k) Fl[v]=-1;
			flow+=k,Edge[e].val-=k,Edge[e^1].val+=k;
		}
	}
	return flow;
}
inline int Dinic()
{
	int r=0,flow;
	while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
	return r;
}
int f[MAXN][MAXN][MAXN];
inline int getId(int x,int y,int z){ return P*Q*(z-1)+Q*(x-1)+y; }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(P,Q,R,D);
	for(int i=1;i<=R;++i)
		for(int j=1;j<=P;++j)
			for(int k=1;k<=Q;++k)
				read(f[j][k][i]);
	S=0,T=P*Q*R+1;
	for(int i=1;i<R;++i)
	{
		for(int j=1;j<=P;++j)
			for(int k=1;k<=Q;++k)
				addEdge(getId(j,k,i),getId(j,k,i+1),f[j][k][i]);
	}
	for(int i=1;i<=P;++i)	
		for(int j=1;j<=Q;++j)
			addEdge(S,getId(i,j,1),INF),addEdge(getId(i,j,R),T,f[i][j][R]);
	for(int i=1;i<=P;++i)
		for(int j=1;j<=Q;++j)
			for(int k=D+1;k<=R;++k)
				for(int l=1;l<=4;++l)
				{
					int ni=i+dx[l],nj=j+dy[l];
					if(ni<1||nj<1||ni>P||nj>Q) continue;
					addEdge(getId(i,j,k),getId(ni,nj,k-D),INF);
				}
	write(Dinic());
	return 0;
}

Draw in Straight Lines

题目简介

题目名称：

题目来源：

评测链接：https://qoj.ac/problem/1197

形式化题意：给定一个 的棋盘，初始全部为白色，你可以执行两种操作：

  1. 将某一个长度为 列或行中所有棋子染色，代价为 ；
  2. 将某一个棋子反色，代价为 。

但操作有两个限制：

  1. 一个棋子至多被染色 次；
  2. 一个棋子被染白后无法被再次染黑。

问到达目标状态的最小代价。

数据范围：

考虑网络流建图，显然操作一为主，操作二作为点缀。分别用 表示一个行或者列是否有被染过色，在这四个函数确定后，算好代价就可以直接实施操作二计算剩余的代价了。

现在关键就在于如何让 和剩下的操作一合起来最优。

首先， 同时贡献肯定是不优的（ 同理），因为无论什么情况都可以省掉其中一步。然后根据目标颜色进行分类讨论。

如果目标状态为黑色，则 ，此时如果 ，则需要执行一次操作二。

如果目标状态为白色，，且如果 或者 ，则需要一次操作二。

然后考虑操作一的计算，也就是让一整列或者一整行纳入贡献，形式类似于最小割，所以直接网络流建图：

  • 当 不同时为 时，连接 ，流量 。
  • 若目标点为黑色
    • 若 ，连接 ，流量 。
    • 若 ，连接 ，流量 。
  • 若目标点为白色
    • 若 ，连接 ，流量 。
    • 若 ，则连接 ，流量 。
  • 若 ，则连接 ，流量 。特别的，连接 ，流量 。
AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// ----- Eternally question-----
// Problem: #1197. Draw in Straight Lines
// Contest: UOJ
// URL: https://qoj.ac/problem/1197
// Memory Limit:  1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-17 15:08:51
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=50,MAXV=1e4+10,MAXE=1e5+10;
const int INF=0x3f3f3f3f;
int N,M,a,b,c,S,T,Idx;
struct Net
{ int next,to,val; }Edge[MAXE<<1];
int Head[MAXV],Cur[MAXV],Total=1;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(Net){Head[u],v,w};Head[u]=Total;
	Edge[++Total]=(Net){Head[v],u,0};Head[v]=Total;
}
int Fl[MAXV];
inline bool Bfs()
{
	std::queue<int>Q;
	std::memset(Fl,-1,sizeof(Fl));
	Fl[S]=1,Cur[S]=Head[S],Q.push(S);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(Fl[v]==-1&&Edge[e].val)
			{
				Fl[v]=Fl[u]+1,Cur[v]=Head[v];
				if(v==T) return 1;
				Q.push(v);
			}
		}
	}
	return 0;
}
int Dfs(int x,int inf)
{
	if(x==T) return inf;
	int flow=0;
	for(int e=Cur[x],v;e&&flow<inf;e=Edge[e].next)
	{
		v=Edge[e].to,Cur[x]=e;
		if(Fl[v]==Fl[x]+1&&Edge[e].val)
		{
			int k=Dfs(v,std::min(Edge[e].val,inf-flow));
			if(!k) Fl[v]=-1;
			flow+=k,Edge[e].val-=k,Edge[e^1].val+=k;
		}
	}
	return flow;
}
inline int Dinic()
{
	int r=0,flow;
	while(Bfs()) while(flow=Dfs(S,INF)) r+=flow;
	return r;
}
char Str[MAXN][MAXN];
int Br[MAXN][MAXN],Bc[MAXN][MAXN],Wr[MAXN][MAXN],Wc[MAXN][MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,a,b,c);
	for(int i=1;i<=N;++i) scanf("%s",Str[i]+1);
	for(int i=1;i<=N;++i)
		for(int j=1;j<=M;++j)
		{
			Br[i][j]=++Idx,Bc[i][j]=++Idx,
			Wr[i][j]=++Idx,Wc[i][j]=++Idx;
		}
	S=++Idx,T=++Idx;
	for(int i=1;i<=N;++i)
		for(int j=1;j<=M;++j)
		{
			addEdge(S,Br[i][j],a),addEdge(S,Wc[i][j],a);
			addEdge(Bc[i][j],T,a),addEdge(Wr[i][j],T,a);
			addEdge(Wr[i][j],Br[i][j],INF),addEdge(Bc[i][j],Wc[i][j],INF);
			if(Str[i][j]=='#')
			{
				addEdge(Wr[i][j],T,INF),addEdge(S,Wc[i][j],INF);
				addEdge(Br[i][j],Bc[i][j],c);
			}
			else
			{
				addEdge(Bc[i][j],Br[i][j],INF);
				addEdge(Wc[i][j],Br[i][j],c),addEdge(Bc[i][j],Wr[i][j],c);
			}
			if(j==1) addEdge(S,Br[i][j],b),addEdge(Wr[i][j],T,b);
			else addEdge(Br[i][j-1],Br[i][j],b),addEdge(Wr[i][j],Wr[i][j-1],b);
			if(i==1) addEdge(Bc[i][j],T,b),addEdge(S,Wc[i][j],b);
			else addEdge(Bc[i][j],Bc[i-1][j],b),addEdge(Wc[i-1][j],Wc[i][j],b);
		}
	write(Dinic());
	return 0;
}
相关文章