题解 NKOJ2929 【[THUSC2014] 函数求解】

代码：

#include <iostream>
#include <queue>
#include <cstdio>
#include <cmath>

using namespace std;

typedef struct {
	int nxt;
	int end;
	int dis;
	double cost;
} Edge;

const int N = 2e3, M = 400 + 7, K = 80800 + 7;
const double eps = 1e-7;
int cnt = 1;
int prime[N + 7], p[M], q[M], head[M], pre_dot[M], pre_edge[M];
double ln[N + 7], dis[M];
bool isnp[N + 7], mark[N + 7], vis[M];
Edge edge[K];
queue<int> que;

inline void init1(){
	int cnt = 0;
	for (register int i = 1; i <= N; i++){
		ln[i] = log(i);
	}
	isnp[0] = isnp[1] = true;
	for (register int i = 2; i <= N; i++){
		if (!isnp[i]) prime[++cnt] = i;
		for (register int j = 1; j <= cnt && i * prime[j] <= N; j++){
			isnp[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
}

inline void init2(int n){
	for (register int i = 0; i <= n; i++){
		dis[i] = 1e9;
	}
}

inline void add_edge(int start, int end, int dis, double cost){
	cnt++;
	edge[cnt].nxt = head[start];
	head[start] = cnt;
	edge[cnt].end = end;
	edge[cnt].dis = dis;
	edge[cnt].cost = cost;
}

inline void spfa(int start){
	dis[start] = 0.0;
	vis[start] = true;
	que.push(start);
	while (!que.empty()){
		int cur = que.front();
		que.pop();
		vis[cur] = false;
		for (register int i = head[cur]; i != 0; i = edge[i].nxt){
			if (edge[i].dis != 0){
				int x = edge[i].end;
				double y = dis[cur] + edge[i].cost;
				if (dis[x] - y > eps){
					dis[x] = y;
					pre_dot[x] = cur;
					pre_edge[x] = i;
					if (!vis[x]){
						vis[x] = true;
						que.push(x);
					}
				}
			}
		}
	}
}

inline double mincost(int n, int start, int end){
	double ans = 0.0;
	while (true){
		init2(n);
		spfa(start);
		if (dis[end] >= 0.0) break;
		int flow = 0x7fffffff;
		for (register int i = end; i != start; i = pre_dot[i]){
			flow = min(flow, edge[pre_edge[i]].dis);
		}
		for (register int i = end; i != start; i = pre_dot[i]){
			edge[pre_edge[i]].dis -= flow;
			edge[pre_edge[i] ^ 1].dis += flow;
		}
		ans += flow * dis[end];
	}
	return ans;
}

int main(){
	int m, d, end;
	double base = 0.0;
	cin >> m >> d;
	init1();
	for (register int i = 1; i <= d; i++){
		cin >> p[i] >> q[i];
		mark[p[i]] = true;
		base += ln[p[i]] * q[i];
	}
	for (register int i = 1, j = 1; i <= d; i++, j++){
		while (mark[prime[j]]) j++;
		p[i + d] = prime[j];
	}
	d *= 2;
	end = d * 2 + 1;
	for (register int i = 1; i <= d; i++){
		int i_ = i + d;
		add_edge(0, i, 1, 0.0);
		add_edge(i, 0, 0, 0.0);
		for (register int j = 1; j <= d; j++){
			double delta = (ln[p[i]] - ln[p[j]]) * (q[j] - q[i]);
			if (delta < 0.0){
				int j_ = j + d;
				add_edge(i, j_, 1, delta);
				add_edge(j_, i, 0, -delta);
			}
		}
		add_edge(i_, end, 1, 0.0);
		add_edge(end, i_, 0, 0.0);
	}
	printf("%.4lf", base + mincost(end, 0, end) / 2.0);
	return 0;
}