给定序列A，序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若 干项，使得4的最长上升子序列长度减少至少1，且付出的代价之和最小，并输出方案。 如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。
输入包含多组数据。 输入的第一行包含整数T，表示数据组数。接下来4*T行描述每组数据。 每组数据的第一行包含一个整数N，表示A的项数，接下来三行，每行N个整数A1．．An，B1．，Bn，C1．．Cn，满足1 < =Ai，Bi，Ci < =10^9，且Ci两两不同。
对每组数据，输出两行。第一行包含两个整数S，M，依次表示删去项的代价和与数量；接下来一行M个整数，表示删去项在4中的的位置，按升序输出。
1 < =N < =700 T < =5
Round 1 Day 2
[ Submit][ Status][ Discuss] 假如没有第二个子问题，那显然是个最小割裸题了 dp出最长上升子序列，然后对于这些可行子序列建边，跑出的最大流就是答案 对于第二问，先考虑对于原图中的一条边，是否可以存在于最小割 残量网络中，一条边可以存在于最小割集，当且仅无法找到任何一条从该边起点到终点的路径 那么就可以贪心地每次选择C最小的边，检查是否可以存在于最小割集，然后删除它的影响 删除影响可以通过删去边，重新跑一遍最大流解决 比较好一点的，是记该边起点为Ai，终点为Bi，跑一遍(Ai,s)最大流，跑一遍(Ai,t)最大流，再删去这条边 听说这是一种叫退流算法的东西。。。？ #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> //#include<ctime> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 1505; const int maxm = 4E5 + 40; typedef int LL; const int INF = ~0U>>1; struct E{ int to; int cap,flow; E(){} E(int to,LL cap,LL flow): to(to),cap(cap),flow(flow){} }edgs[maxm]; struct data{ int Num,key; data(){} data(int Num,int key): Num(Num),key(key){} bool operator < (const data &B) const {return key < B.key;} }D[maxn]; int n,m,tot,cnt,Cnt,T,s,t,tp,Ans[maxn],A[maxn],B[maxn],cur[maxn] ,L[maxn],f[maxn],a[maxn],b[maxn],id[maxn],vis[maxn]; vector <int> v[maxn]; queue <int> Q; int getint() { char ch = getchar(); int ret = 0; while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') ret = ret * 10 + ch - '0',ch = getchar(); return ret; } char ch[20]; void Print(LL x) { if (!x) {putchar('0'); return;} int len = 0; while (x) ch[++len] = x % 10LL,x /= 10LL; for (int i = len; i; i--) putchar(ch[i] + '0'); } bool BFS(int ss,int tt) { for (int i = 0; i <= tot; i++) L[i] = 0; Q.push(ss); L[ss] = 1; while (!Q.empty()) { int k = Q.front(); Q.pop(); for (int i = 0; i < v[k].size(); i++) { E e = edgs[v[k][i]]; if (e.cap == e.flow || L[e.to]) continue; L[e.to] = L[k] + 1; Q.push(e.to); } } return L[tt]; } LL Dinic(int x,LL res,int tt) { if (x == tt) return res; LL flow = 0; for (int &i = cur[x]; i < v[x].size(); i++) { E &e = edgs[v[x][i]]; if (e.cap == e.flow || L[e.to] != L[x] + 1) continue; LL f = Dinic(e.to,min(res,e.cap - e.flow),tt); if (!f) continue; flow += f; e.flow += f; edgs[v[x][i]^1].flow -= f; res -= f; if (!res) return flow; } if (!flow) L[x] = -1; return flow; } LL MaxFlow(int ss,int tt) { LL ret = 0; while (BFS(ss,tt)) { for (int i = 0; i <= tot; i++) cur[i] = 0; ret += Dinic(ss,INF,tt); } return ret; } bool Check(int x) { vis[A[x]] = ++Cnt; Q.push(A[x]); while (!Q.empty()) { int k = Q.front(); Q.pop(); for (int i = 0; i < v[k].size(); i++) { E e = edgs[v[k][i]]; if (e.cap == e.flow || vis[e.to] == Cnt) continue; vis[e.to] = Cnt; Q.push(e.to); } } return vis[B[x]] != Cnt; } void Work(int x) { MaxFlow(t,B[x]); MaxFlow(A[x],s); edgs[id[x]].cap = edgs[id[x]].flow = 0; edgs[id[x]^1].cap = edgs[id[x]^1].flow = 0; } void Add(int x,int y,LL cap) { v[x].push_back(cnt); edgs[cnt++] = E(y,cap,0); v[y].push_back(cnt); edgs[cnt++] = E(x,0,0); } void Clear() { for (int i = 0; i <= tot; i++) v[i].clear(); memset(f,0,sizeof(f)); tot = tp = cnt = 0; } void Solve() { n = getint(); int Max = 0; for (int i = 1; i <= n; i++) A[i] = ++tot,B[i] = ++tot; t = ++tot; for (int i = 1; i <= n; i++) a[i] = getint(); for (int i = 1; i <= n; i++) b[i] = getint(); for (int i = 1; i <= n; i++) D[i] = data(i,getint()); sort(D + 1,D + n + 1); for (int i = 2; i <= n; i++) { for (int j = 1; j < i; j++) if (a[i] > a[j]) f[i] = max(f[i],f[j] + 1); Max = max(Max,f[i]); } for (int i = 1; i <= n; i++) if (f[i] == Max) Add(B[i],t,INF); for (int i = 1; i <= n; i++) { if (!f[i]) Add(s,A[i],INF); for (int j = i + 1; j <= n; j++) if (a[i] < a[j] && f[i] + 1 == f[j]) Add(B[i],A[j],INF); Add(A[i],B[i],b[i]); id[i] = cnt - 1; } LL sum = MaxFlow(s,t); //cerr << (double)(clock()) / CLOCKS_PER_SEC << endl; for (int i = 1; i <= n; i++) if (Check(D[i].Num)) { Work(D[i].Num); Ans[++tp] = D[i].Num; //cerr << (double)(clock()) / CLOCKS_PER_SEC << endl; } sort(Ans + 1,Ans + tp + 1); Print(sum); putchar(' '); Print(tp); puts(""); for (int i = 1; i < tp; i++) Print(Ans[i]),putchar(' '); Print(Ans[tp]); puts(""); Clear(); } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif T = getint(); while (T--) Solve(); //cerr << (double)(clock()) / CLOCKS_PER_SEC << endl; return 0; }