Luogu

分析

很套路的费用流。

把每个点 $i$ 拆成 $i$ 和 $i'$ ,然后这样连边:

  • 源点向 $i$ 连容量为 $1$ 、费用为 $0$ 的边。
  • $i'$ 向汇点连容量为 $1$ 、费用为 $0$ 的边。
  • 源点向 $i'$ 连容量为 $1$ 、费用为 $a_i$ 的边。
  • 对于一条边 $(u,v,w)$ ,$u$ 向 $v'$ 连容量为 $1$ 、费用为 $w$ 的边。

跑最小费用最大流即可。

感觉本质上和最小路径覆盖是一样的?

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n,m,s,t;

struct edge { int v,w,c,nxt; } e[1000000];
int head[100000];
inline void addEdge(int u,int v,int w,int c) {
    static int cnt=1;
    e[++cnt]=(edge){v,w,c,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,0,-c,head[v]},head[v]=cnt;
}

int dis[100000],inq[100000],lst[100000];
inline int spfa() {
    memset(dis,0x3f,(t+1)<<2),memset(lst,0,(t+1)<<2);
    queue<int> Q; Q.push(s),dis[s]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(),inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w,c=e[i].c;
            if (w&&dis[u]+c<dis[v]) {
                dis[v]=dis[u]+c,lst[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return lst[t]!=0;
}

int main() {
    n=read(),m=read(),s=0,t=n+n+1;
    for (re int i=1;i<=n;++i) addEdge(s,i,1,0);
    for (re int i=1;i<=n;++i) addEdge(i+n,t,1,0);
    for (re int i=1;i<=n;++i) addEdge(s,i+n,1,read());
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        if (u>v) swap(u,v);
        addEdge(u,v+n,1,w);
    }
    int ans=0;
    while (spfa()) {
        int f=2e9;
        for (re int i=lst[t];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=lst[t];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        ans+=dis[t]*f;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 32 PM