相关链接
题目传送门:http://codeforces.com/contest/802/problem/C
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
消圈定理:https://blog.sengxian.com/algorithms/clearcircle
解题报告
被这题强制解锁了两个新姿势qwq
- 上下界最小费用流:
直接按照上下界网络流一样建图,然后正常跑费用流- 带负环的费用流
应用消圈定理,强行将负环满流
然后考完之后发现脑残了
换一种建图方法就没有负环了_(:з」∠)_
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 5000000; const int M = 200; const int INF = 1e9; int n,k,S,T,tot,SS,TT,ans,a[M],np[M],cc[M]; int head[N],nxt[N],to[N],flow[N],cost[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline int AddEdge(int u, int v, int c, int f) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c; to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c; } class Minimum_Cost_Flow{ int dis[N],sur[N],inq[N],vis[N]; queue<int> que; public: inline void MaxFlow() { while (clearCircle()); for (int ff; ff = INF, SPFA();) { for (int w = TT; w != SS; w = to[sur[w]^1]) { ff = min(ff, flow[sur[w]]); } for (int w = TT; w != SS; w = to[sur[w]^1]) { flow[sur[w]] -= ff; flow[sur[w]^1] += ff; } ans += dis[TT] * ff; } } private: bool SPFA() { memset(dis,60,sizeof(dis)); que.push(SS); dis[SS] = 0; while (!que.empty()) { int w = que.front(); que.pop(); inq[w] = 0; for (int i=head[w];i;i=nxt[i]) { if (dis[to[i]] > dis[w] + cost[i] && flow[i]) { dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i; if (!inq[to[i]]) { inq[to[i]] = 1; que.push(to[i]); } } } } return dis[TT] < INF; } bool clearCircle() { memset(dis, 0, sizeof(dis)); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= tot; ++i) { if (!vis[i] && DFS(i)) { return 1; } } return 0; } bool DFS(int w) { vis[w] = 1; if (inq[w]) { int cur = w; do { flow[sur[cur]]--; flow[sur[cur]^1]++; ans += cost[sur[cur]]; cur = to[sur[cur]]; } while (cur != w); return 1; } else { inq[w] = 1; for (int i = head[w]; i; i = nxt[i]) { if (flow[i] && dis[to[i]] > dis[w] + cost[i]) { dis[to[i]] = dis[w] + cost[i]; sur[w] = i; if (DFS(to[i])) { inq[w] = 0; return 1; } } } inq[w] = 0; return 0; } } }MCMF; int main() { #ifdef DBG freopen("11input.in", "r", stdin); #endif n = read(); k = read(); S = tot = n + 4; T = n + 1; SS = n + 2; TT = n + 3; AddEdge(T, S, 0, k); AddEdge(S, 1, 0, INF); for (int i = 1; i <= n; i++) { np[i] = ++tot; AddEdge(np[i], i + 1, 0, INF); AddEdge(i, np[i], 0, INF); AddEdge(i, TT, 0, 1); AddEdge(SS, np[i], 0, 1); a[i] = read(); } for (int i = 1; i <= n; i++) { cc[i] = read(); } for (int i = 1; i <= n; i++) { ans += cc[a[i]]; for (int j = i + 1; j <= n; j++) { if (a[i] == a[j]) { AddEdge(np[i], j, -cc[a[i]], 1); break; } } } MCMF.MaxFlow(); cout<<ans<<endl; return 0; }