相关链接
题目传送门：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;
}
