TLE 22pts 求助
查看原帖
TLE 22pts 求助
679961
zhang_kevin楼主2024/12/25 19:34
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		x = (x<<1) + (x<<3) + (ch^48);
		ch = getchar();
	}
	return x * f;
}
const int N = 100001, M = 5000001, inf = 1e18 + 998244353 + 114514;
struct Edge{
	int to, nxt;
	int w;
}e[M];
int head[N], tot = 1;
inline void add_edge(int u, int v, int w){
	tot++;
	e[tot].to = v;
	e[tot].nxt = head[u];
	e[tot].w = w;
	head[u] = tot;
	return;
}
inline void add(int u, int v, int w){
	add_edge(u, v, w);
	add_edge(v, u, 0);
	return;
}
int n, s, t, dis[N], cur[N];
inline bool bfs(){
	for(int i = 1; i <= n; i++) dis[i] = inf;
	queue<int> q;
	q.push(s), dis[s] = 0, cur[s] = head[s];
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int i = head[u]; i; i = e[i].nxt){
			int v = e[i].to;
			if(dis[v] == inf && e[i].w > 0){
				dis[v] = dis[u] + 1, cur[v] = head[v];
				if(v == t) return true;
				q.push(v);
			}
		}
	}
	return false;
}
inline int dfs(int u, int sum){
	if(u == t) return sum;
	int res = 0;
	for(int i = cur[u]; i; i = e[i].nxt){
		int v = e[i].to;
		cur[u] = i;
		if(dis[v] == dis[u] + 1 && e[i].w){
			int k = dfs(v, min(sum, e[i].w));
			e[i].w -= k, e[i^1].w += k;
			res += k, sum -= k;
		}
	}
	return res;
}
inline int Dinic(){
	int ans = 0;
	while(bfs()){
		ans += dfs(s, inf);
	}
	return ans;
}
signed main(){
	int nn = read();
	vector<int> a(nn+1), b(nn+1);
	int sum = 0;
	for(int i = 1; i <= nn; i++) sum += a[i] = read();
	for(int i = 1; i <= nn; i++) sum += b[i] = read();
	int mm = read();
	vector<int> p(mm+1), q(mm+1);
	vector<vector<int> > products(mm+1);
	for(int i = 1; i <= mm; i++){
		products[i].push_back(read());
		sum += p[i] = read(); sum += q[i] = read();
		for(int j = 1; j <= products[i][0]; j++) products[i].push_back(read());
	}
	n = nn + mm + mm + 2;
	s = nn + mm + mm + 1;
	t = nn + mm + mm + 2;
	for(int i = 1; i <= nn; i++) add(s, i, a[i]), add(i, t, b[i]);
	for(int i = 1; i <= mm; i++){
		add(s, nn+i, p[i]), add(nn+mm+i, t, q[i]);
		for(int j = 1; j <= products[i][0]; j++){
			add(nn+i, products[i][j], inf);
			add(products[i][j], nn+mm+i, inf);
		}
	}
	cout << sum - Dinic() << endl;
	return 0;
}
2024/12/25 19:34
加载中...