「SDOI2014」LIS - LIS+拆点+最小割 | Bill Yang's Blog

「SDOI2014」LIS - LIS+拆点+最小割

题目大意

    给定序列$A$,序列中的每一项$A_i$有删除代价$B_i$和附加属性$C_i$。请删除若干项,使得$A$的最长上升子序列长度减少至少$1$,且付出的代价之和最小,并输出方案。
    如果有多种方案,请输出将删去项的附加属性排序之后,字典序最小的一种。


题目分析

先求出LIS,将可能的LIS转移路径用建成网络流图。
即,每个点拆成入点和出点,入出点连边$B_i$表示割掉的代价。
按照LIS转移路径从出点到入点连边,$f_i=1$的从$S$连边,$f_i=Max_f$的向$T$连边。
最大流就是第一问答案。
到这里都很显然。

第二问可以按照$C_i$从小到大的顺序依次删边验证最大流是否变小来确定割集,但会TLE。
考虑,删去$u\rightarrow v$最大流是否会变小即当前残余网络是否还能从$u\rightarrow v$,若不能,删去后一定会变小,加入割集。

为了排除其他割集的影响,若确定一条边在割集内,需要将其从残余网络中删除,并用网络流更新残余网络。
然而,这样依然会TLE。
考虑退流算法,在残余网络中从$T$到$v$跑一次最大流,从$u$到$S$跑一次最大流,即可删除影响。
正确性在于因为$u$不能到达$v$,因此$u$不能到达$T$,而$v$显然也不能到达$T$,故不会对其他路径产生影响。

然后就可以卡常了,发现我的dinic竟然还可以优化,已加入代码库


代码

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
140
141
142
143
144
145
146
147
148
149
150
#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 maxn=1405;
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[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
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() {
for(int i=1; i<=n; i++)vst[i]=0;
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;
if(Next==s)return 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;
struct node {
int v,id;
bool operator < (const node& b) const {
return v<b.v;
}
} c[maxn];
int n,a[maxn],b[maxn],f[maxn],Max=0;
vector<int> ans;
int main() {
int t=Get_Int();
while(t--) {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=n; i++)b[i]=Get_Int();
for(int i=1; i<=n; i++)c[i].v=Get_Int(),c[i].id=i;
Max=0;
for(int i=1; i<=n; i++) {
f[i]=1;
for(int j=1; j<i; j++)if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
Max=max(Max,f[i]);
}
int S=n*2+1,T=n*2+2;
dinic.init(T);
for(int i=1; i<=n; i++)dinic.AddEdge(i,n+i,b[i]);
for(int i=1; i<=n; i++)if(f[i]==1)dinic.AddEdge(S,i,INT_MAX/2);
for(int i=1; i<=n; i++)if(f[i]==Max)dinic.AddEdge(n+i,T,INT_MAX/2);
for(int i=1; i<=n; i++)
for(int j=1; j<i; j++)
if(a[j]<a[i]&&f[i]==f[j]+1)dinic.AddEdge(n+j,i,INT_MAX/2);
int ans1=dinic.maxflow(S,T);
sort(c+1,c+n+1);
ans.clear();
for(int i=1; i<=n; i++) {
int u=c[i].id,v=n+c[i].id;
dinic.s=u,dinic.t=v;
if(dinic.bfs())continue;
dinic.maxflow(T,v),dinic.maxflow(u,S);
ans.push_back(c[i].id);
}
sort(ans.begin(),ans.end());
printf("%d %d\n",ans1,ans.size());
for(int x:ans)printf("%d ",x);
putchar('\n');
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%