隐藏
「SHOI2017」寿司餐厅 - 最大权闭合子图 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「SHOI2017」寿司餐厅 - 最大权闭合子图

题目大意

    有一些寿司排成一行,每个寿司有一个代号$a[]$,寿司的美味度$d[i,j]$定义为将$i\rightarrow j$一次性取走的价值。每次可以取走一段连续的寿司,获得所有其包含的美味度(如取走$[1,2]$,则累加$d[1,1]+d[2,2]+d[1,2]$),连续一段的美味度不重复计算(以后取寿司不继续累加$d[1,1],d[2,2],d[1,2]$)。取走$c$份代号为$i$的寿司需要付出$mx^2+cx$元,$m$是给定的常数,求可以获得的美味度减去花费的最大值。


题目分析

看到美味度减去花费就可以想到最大权闭合子图了。

因为花费有个平方项,但平方项与取的次数无关,故将代号单独提出建立点。
每个代号向$T$连边,容量为平方项的值。

对于美味度的处理:若取走$d[1,2]$,就必须取走$d[1,1],d[2,2]$,将它们连边即可,容量$inf$。

每个寿司向其代号连边,容量$inf$,并向$T$连边,容量为其代号。
根据每个寿司的美味度决定其与$S$还是与$T$连边。
这里也可以直接将每个寿司的美味度减去其代号,就不需要和$T$连容量为代号的边了。

最后建图如下:

建图方式1:

建图方式2:


代码

建图方式1

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxnode=11005,maxn=105,maxid=1005;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxnode];
bool vst[maxnode];
int dist[maxnode],cur[maxnode];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t); //reversed
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

int n,m,cnt=0,sum=0,id[maxn],num[maxn][maxn],vst[maxid];

int main() {
n=Get_Int();
m=Get_Int();
int S=n*n+1000,T=S+1;
for(int i=1; i<=n; i++) {
id[i]=Get_Int();
cnt=max(cnt,id[i]);
if(!vst[id[i]]) {
dinic.AddEdge(id[i],T,m*id[i]*id[i]);
vst[id[i]]=1;
}
}
for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++) {
num[i][j]=++cnt;
int v=Get_Int();
if(v>=0) {
dinic.AddEdge(S,num[i][j],v);
sum+=v;
} else dinic.AddEdge(num[i][j],T,-v);
}
for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++) {
if(num[i][j-1])dinic.AddEdge(num[i][j],num[i][j-1],INT_MAX);
if(num[i+1][j])dinic.AddEdge(num[i][j],num[i+1][j],INT_MAX);
}
for(int i=1; i<=n; i++) {
dinic.AddEdge(num[i][i],T,id[i]);
dinic.AddEdge(num[i][i],id[i],INT_MAX);
}
printf("%d\n",sum-dinic.maxflow(S,T));
return 0;
}

建图方式2

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxnode=11005,maxn=105,maxid=1005;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxnode];
bool vst[maxnode];
int dist[maxnode],cur[maxnode];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t); //reversed
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

int n,m,cnt=0,sum=0,id[maxn],num[maxn][maxn],vst[maxid];

int main() {
n=Get_Int();
m=Get_Int();
int S=n*n+1000,T=S+1;
for(int i=1; i<=n; i++) {
id[i]=Get_Int();
cnt=max(cnt,id[i]);
if(!vst[id[i]]) {
dinic.AddEdge(id[i],T,m*id[i]*id[i]);
vst[id[i]]=1;
}
}
for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++) {
num[i][j]=++cnt;
int v=Get_Int();
if(i==j) {
v-=id[i];
dinic.AddEdge(num[i][i],id[i],INT_MAX);
}
if(v>=0) {
dinic.AddEdge(S,num[i][j],v);
sum+=v;
} else dinic.AddEdge(num[i][j],T,-v);
}
for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++) {
if(num[i][j-1])dinic.AddEdge(num[i][j],num[i][j-1],INT_MAX);
if(num[i+1][j])dinic.AddEdge(num[i][j],num[i+1][j],INT_MAX);
}
printf("%d\n",sum-dinic.maxflow(S,T));
return 0;
}

姥爷们赏瓶冰阔落吧~