代码 TLE 44 分,玄关求调
查看原帖
代码 TLE 44 分,玄关求调
1399394
wpl123456wpl楼主2025/7/10 21:30
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3e3 + 5, M = 5e6 + 5, INF = 1e7;

int n, m, a[N], b[N], t, len, h[N], top = 1, ans, sum;
int dis[N], cur[N];
vector<int> c;

struct edge{
    int v, next, w;
}g[M];

void addedge(int u, int v, int w){
    g[++top] = {v, h[u], w}, h[u] = top;
}

queue<int> q;
bool bfs(){
    for(int i = 0; i <= len; i++){
        dis[i] = INF, cur[i] = h[i];
    }
    q.push(0), dis[0] = 0;
    while(q.size()){
        int u = q.front();
        q.pop();
        for(int i = h[u]; i; i = g[i].next){
            int v = g[i].v, w = g[i].w;
            if(!w || dis[v] != INF) continue;
            dis[v] = dis[u] + 1, q.push(v);
        }
    }
    return dis[t] != INF;
}

int dfs(int u, int sum){
    if(u == t) return sum;
    int res = 0;
    for(int i = cur[u]; i && res != sum; i = g[i].next){
        int v = g[i].v, w = g[i].w;
        cur[u] = h[u];
        if(!w || dis[v] != dis[u] + 1) continue;
        int cnt = dfs(v, min(sum - res, w));
        res += cnt, g[i].w -= cnt, g[i ^ 1].w += cnt;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i], sum += a[i];
        addedge(0, i, a[i]), addedge(i, 0, 0);
    }
    t = len = n + 1;
    for(int i = 1; i <= n; i++){
        cin >> b[i], sum += b[i];
        addedge(i, t, b[i]), addedge(t, i, 0);
    }
    cin >> m;
    for(int i = 1, k, ad, bd; i <= m; i++){
        cin >> k >> ad >> bd;
        for(int j = 1, v; j <= k; j++){
            cin >> v;
            c.push_back(v);
        }
        sum += ad + bd;
        ++len;
        for(int d : c) addedge(len, d, INF), addedge(d, len, 0);
        addedge(0, len, ad), addedge(len, 0, 0);
        ++len;
        for(int d : c) addedge(d, len, INF), addedge(len, d, 0);
        addedge(len, t, bd), addedge(t, len, 0);
        c.clear();
    }
    while(bfs()){
        ans += dfs(0, INF);
    }
    cout << sum - ans;
    return 0;
}

如果调好了,麻烦@一下我,^_^。Thanks you.

2025/7/10 21:30
加载中...