BZOJ3532 Lis

发表于

  题意:一个三元组序列$(A_i, B_i, C_i)$，求删掉若干项，使剩下项关于$A_i$的最长上升子序列长度减少1，并使得删去项$B_i$之和最小。输出最小值以及删去项按$C_i$排序后的字典序最小的方案。

  这道题如果不输出方案，那么就是一个最小割。首先每一项拆成两个点，中间连权值为删去费用$B_i$的边。将每一项按照$A_i$的dp关系，$A_i < A_j$ 且 $dp_i + 1 = dp_j$ ，即i能转移到j，则i向j连INF边。$dp_i = 1$的由原点向i连INF边，$dp_i = Max$的由i向汇点连INF边。最小割就是答案。
  输出方案的话，我们考虑所有最大流之后满流且两端点互不可达的边，只有这些边可能且一定在最小割的某个可行方案中。因为要求字典序最小，我们便从最小的边开始枚举起。枚举到一条边满足条件后，便贪心地加入答案，并且去掉这条边的影响。即该边被割后，其他一些边就没有必要割了，这些边就要排除在条件之外。
  怎么排除?退流。例如我们选中一条边$(u, v)$，我们由汇至v，u至源分别再跑一遍网络流，就可以退掉与$(u, v)$相关的流。相当于在原图中没有出现过$(u, v)$这条边，这时还需要割的边再继续考虑下去即可。

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define erep(i, u) for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define ms(a, b) memset(a, b, sizeof a);
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c - '0'; isdigit(c = getchar()); (x *= 10) += c - '0');
    if(flag) x = -x; return x;
}
const int maxN = 710, INF = 0x3f3f3f3f, maxn = 1410, maxm = 600010;
int n;
int a[maxN], b[maxN];
int f[maxN];
struct info
{
	int val, id;
	bool operator < (const info& rhs) const { return val < rhs.val; }
} C[maxN];
int head[maxn], nxt[maxm << 1], to[maxm << 1], c[maxm << 1], e;
void ae(int x, int y, int w) { to[++e] = y; nxt[e] = head[x]; head[x] = e; c[e] = w; }
namespace dinic
{
	int S, T, dis[maxn], cur[maxn];
	bool bfs()
	{
		queue<int> q; q.push(S);
		ms(dis, 0); dis[S] = 1;
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			erep(i, u) if(c[i] && !dis[v]) dis[v] = dis[u] + 1, q.push(v);
		}
		return dis[T];
	}
	int dfs(int u, int flow)
	{
		if(u == T) return flow;
		int res = flow;
		for(int& i = cur[u]; i; i = nxt[i])
		{
			int v = to[i];
			if(c[i] && dis[u] + 1 == dis[v])
			{
				int d = dfs(v, min(c[i], res));
				c[i] -= d; c[i ^ 1] += d;
				res -= d; if(!res) return flow;
			}
		}
		return flow - res;
	}
	int maxflow(int s, int t)
	{
		S = s, T = t; int flow = 0;
		while(bfs())
		{
			memcpy(cur, head, sizeof head);
			flow += dfs(S, INF);
		}
		return flow;
	}
}
bool vis[maxn];
bool bfs(int s, int t)
{
	queue<int> q; q.push(s);
	ms(vis, 0); vis[s] = 1;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		if(u == t) return 1;
		erep(i, u) if(c[i] && !vis[v]) vis[v] = 1, q.push(v);
	}
	return 0;
}
vector<int> ans;
void init()
{
	ms(head, 0); e = 1;
	ms(f, 0); ans.clear();
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
	int _; read(_);
	while(_--)
	{
		init();
		read(n); int tmp = 0;
		rep(i, 1, n) read(a[i]);
		rep(i, 1, n) read(b[i]);
		rep(i, 1, n) read(C[i].val), C[i].id = i;
		
		rep(i, 1, n) rep(j, 0, i - 1) if(a[j] < a[i]) chkmax(f[i], f[j] + 1);
		rep(i, 1, n) chkmax(tmp, f[i]);
		rep(i, 1, n) ae(i, n + i, b[i]), ae(n + i, i, 0);
		rep(i, 1, n) if(f[i] == 1) ae(0, i, INF), ae(i, 0, 0);
		rep(i, 1, n) if(f[i] == tmp)
			ae(n + i, 2 * n + 1, INF), ae(2 * n + 1, n + i, 0);
		rep(i, 1, n) rep(j, i + 1, n)
			if(a[i] < a[j] && f[i] + 1 == f[j]) ae(n + i, j, INF), ae(j, n + i, 0);
		printf("%d ", dinic::maxflow(0, 2 * n + 1));
		sort(C + 1, C + n + 1);
		rep(i, 1, n)
		{
			int x = C[i].id;
			if(c[x * 2] || bfs(x, x + n)) continue;
			ans.pb(x);
			dinic::maxflow(2 * n + 1, x + n);
			dinic::maxflow(x, 0);
			c[x * 2] = c[x * 2 + 1] = 0;
		}
		printf("%d\n", SZ(ans)); sort(ALL(ans));
		rep(i, 0, SZ(ans) - 1) printf("%d%c", ans[i], (i == SZ(ans) - 1) ? '\n' : ' ');
	}
	return 0;
}