【Codeforces 802C】Heidi and Library (hard)

相关链接

题目传送门：http://codeforces.com/contest/802/problem/C
官方题解：http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
消圈定理：https://blog.sengxian.com/algorithms/clearcircle

解题报告

被这题强制解锁了两个新姿势qwq

1. 上下界最小费用流：
   直接按照上下界网络流一样建图，然后正常跑费用流
2. 带负环的费用流
   应用消圈定理，强行将负环满流

然后考完之后发现脑残了
换一种建图方法就没有负环了_(:з」∠)_

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;
}