P4068 [SDOI2016]数字配对

增广时费用为负停掉即可 注意开long long

#include 
using namespace std;
//using ll = long long;

#define int long long
const int V = 201000;
const int E = 2010000;

template<typename T>
struct MinCostGraph {
	int s, t, vtot;
	int h[V], idx;
	T d[V], flow, cost;
	int pre[V];
	bool vis[V];
	int f[E * 2];
	int w[E * 2];
	int e[E * 2];
	int ne[E * 2];
	void add(int a, int b, int c, int d) {
		e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
		e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
	}

	bool spfa() {
		T inf = numeric_limits<T>::max() / 2;
		for (int i = 1; i <= vtot; i++) {
			d[i] =  inf;
			vis[i] = false;
			pre[i] = -1;
		}
		d[s] = 0;
		vis[s] = true;
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			vis[u] = false;
			for(int i = h[u]; ~i; i = ne[i]) {
				int v = e[i];
				if (f[i] && d[v] > d[u] + w[i]) {
					d[v] = d[u] + w[i];
					pre[v] = i;
					if (!vis[v]) {
						vis[v] = 1;
						q.push(v);
					}
				}
			}
		}
		return d[t] != inf;
	}
	int  fl = 0;
	void augment() {
		int u = t;
		T q = numeric_limits<T>::max();
		while (~pre[u]) {
			q = min(q, 1ll * f[pre[u]]);
			u = e[pre[u] ^ 1];
		}
		int tot = cost;
		int www = flow;
		//flow += q;
		if(tot + q * d[t] > 0) {
			flow +=  -tot / (d[t]);
			fl = 1;
			return ;
		}
		flow += q;
		cost += q * d[t];
		u = t;
		while (~pre[u]) {
			f[pre[u]] -= q;
			f[pre[u] ^ 1] += q;
			u = e[pre[u] ^ 1];
		}
	}

	pair<T, T> solve() {
		flow = 0;
		cost = 0;
		while (spfa() && !fl) augment();
		return {flow, cost};
	}
	void init(int s_, int t_, int vtot_) {
		s = s_;
		t = t_;
		vtot = vtot_;
		idx = 0;
		for (int i = 1; i <= vtot; i++) h[i] = -1;
	}
};

MinCostGraph<int> g;
int n, m;
int S, T;
const int N = 2e5 + 10;
int cnt[N];
int idx , p[N], v[N];
void init(int n ) {
	for(int i = 2; i <= n; i++) {
		if(!v[i])p[++idx] = i;
		for(int j = 1; j <= idx && i * p[j] <= n; j++) {
			v[i * p[j]] = 1;
			if(i % p[j] == 0)break;
		}
	}
}
int work(int n) {
	int t = 0;
	for(int i = 1; p[i]*p[i] <= n; i++) {
		if(n % p[i] == 0) {
			while(n % p[i] == 0) n /= p[i], t++;
		}
	}
	if(n > 1)t++;
	return t;
}
int a[N], b[N], c[N];
signed main() {

	init(N - 10);
	cin >> n;
	S = n + 1;
	T = n + 2;
	g.init(S, T, T);
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= n; i++) cin >> c[i];
	for(int i = 1; i <= n; i++)cnt[i] = work(a[i]);
	//for(int i = 1; i <= n; i++)cout << cnt[i] << " \n"[i == n];
	for(int i = 1; i <= n; i++) if(cnt[i] & 1) g.add(S, i, b[i], 0);
		else  g.add(i, T, b[i], 0);
	for(int i = 1; i <= n; i++) if(cnt[i] & 1) {
			for(int j = 1; j <= n; j++) {
				if(cnt[j] & 1)continue;
				if((cnt[i] + 1 == cnt[j] && a[j] % a[i] == 0) || (cnt[j] + 1 == cnt[i] && a[i] % a[j] == 0)) {
					g.add(i, j, 1ll << 60,  -1ll * c[i]*c[j]);
				}
			}
		}
	pair<int, int>t;
	t = g.solve();
	cout << t.first << endl;

}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151