题解 P2469 【[SDOI2010]星际竞速】

· · 题解

说一个与众不同的建图法。

首先我们假设所有的点都是直接跳跃过去的，此时代价是sigma ai。

然后我们考虑走图上的一条边意味着什么？

我们要付出边权的代价，但同时终点就不需要通过跳跃到达了，因此会省下终点点权的代价。

再考虑原始的最小路径覆盖，每条匹配边对应原图上一条选中的边。

而在本问题中，每一对匹配的终点的点权是会省下的。

所以我们可以这样建图：

每个点拆成两个点i和i'，s向i连边，容量1费用0，i'向t连边，容量1费用-ai，对于原图上的一条边(u,v)，u向v'连边，容量1费用为边权。

此时我们只需要用点权和减去这张图的最小费用流(不是最小费用最大流，即当汇点的dis>=0时直接退出)即可。

亲测跑得比其他建图法略快一些。

#include<bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pc putchar
#define li long long
inline li read(){
    li x = 0,y = 0,c = gc;
    while(!isdigit(c)) y = c,c = gc;
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'),c = gc;
    return y == '-' ? -x : x;
}
inline void print(li q){
    if(q < 0) pc('-'),q = -q;
    if(q >= 10) print(q / 10);
    pc(q % 10 + '0');
}
int n,m,a[2010],s,g,h,t,q[200010];
struct edge{
    int to,nxt,val,cst;
}e[50010];
int cnt = 1,fir[2010],dq[2010],dis[2010],ans;
bool inq[2010];
inline void ins(int u,int v,int w,int x){
    e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;e[cnt].val = w;e[cnt].cst = x;
    e[++cnt].to = u;e[cnt].nxt = fir[v];fir[v] = cnt;e[cnt].val = 0;e[cnt].cst = -x;
}
#define inf 987654321
bool bfs(){
    int i,j;
    h = t = 0;
    for(i = 1;i <= g;++i) dis[i] = inf,inq[i] = 0;
    dis[s] = 0;q[++t] = s;inq[s] = 1;
    while(h < t){
        j = q[++h];inq[j] = 0;
        for(i = fir[j];i;i = e[i].nxt) if(e[i].val > 0){
            if(dis[e[i].to] > dis[j] + e[i].cst){
                dis[e[i].to] = dis[j] + e[i].cst;
                if(!inq[e[i].to]){
                    inq[e[i].to] = 1;
                    q[++t] = e[i].to;
                }
            }
        }
    }
    return dis[g] < 0;
}
bool vis[2010];
int dfs(int q,int fl){
    if(q == g) return fl;
    vis[q] = 1;
    int as = 0,tp;
    for(int &i = dq[q];i;i = e[i].nxt) if(e[i].val > 0 && !vis[e[i].to] && dis[e[i].to] == dis[q] + e[i].cst){
        tp = dfs(e[i].to,min(fl,e[i].val));
        fl -= tp;as += tp;
        e[i].val -= tp;e[i ^ 1].val += tp;
        if(!fl){
            vis[q] = 0;return as;
        }
    }
    return as;
}
int wk(){
    int as = 0,tp;
    while(bfs()){
        for(int i = 1;i <= g;++i) dq[i] = fir[i],vis[i] = 0;
        while((tp = dfs(s,inf)) != 0) as += dis[g] * tp;
    }
    return as;
}
int main(){
    int i,u,v,w;
    n = read();m = read();
    for(i = 1;i <= n;++i) a[i] = read(),ans += a[i];
    s = n * 2 + 1;g = n * 2 + 2;
    for(i = 1;i <= n;++i) ins(s,i,1,0),ins(i + n,g,1,-a[i]);
    for(i = 1;i <= m;++i){
        u = read();v = read();w = read();
        if(u > v) swap(u,v);
        ins(u,v + n,1,w);
    }
    print(ans + wk());
    return 0;
}