BZOJ 1497: [NOI2006]最大获利 – [网络流/最大权闭合图]

题目传送门(BZOJ)
>原文链接<

题解 :

最大权闭合图 : 选了一个点,那么这个点可到达的所有点都要选, 求最大点权和。

建图套路 :

  1. 源点连正权点,边权为正权点权。
  2. 负权点连汇点,边权为点权相反数。
  3. 原图有的边连边,权值为INF。

答案就是正权点权和-最小割(即最大流)

对于本题来说,负权就是代价 P_i 正权就是获利 C_i 。按以上套路连点即可。

具体的,

i \to T \; val = p[i]

S \to i+n\; val = c[i]

i+n\to a[i]\; val = INF

i+n \to b[i]\; val = INF

代码 :

#include 
#include 
#include 
#include 
#include 
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)
using namespace std;
char buf[100000],*p1,*p2;
inline int rd() {
    int x = 0; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc();
    return x;
}
const int N = 210000;
const int S = N-1, T = S-1;
const int INF = 1<<30;
struct Edge {
    int to, val;
    Edge *next, *back;
}*h[N],e[N<<1];
inline void Add_Edge(int u, int v, int w) {
    static int _;
    Edge *tmp = &e[++_];
    tmp->to = v; tmp->val = w; tmp->next = h[u]; tmp->back = &e[_+1]; h[u] = tmp;
    tmp = &e[++_];
    tmp->to = u; tmp->val = 0; tmp->next = h[v]; tmp->back = &e[_-1]; h[v] = tmp;

}
queue q;
int dep[N];
bool bfs() {
    while(!q.empty()) q.pop();
    memset(dep, 0, sizeof dep);
    dep[S] = 1;
    q.push(S);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        rev(i, u) if(!dep[i->to] && i->val) {
            dep[i->to] = dep[u] + 1;
            if(i->to == T) return 1;
            q.push(i->to);
        }
    }
    return 0;
}
int dfs(int p, int mf) {
    if(p == T) return mf;
    int nf = 0;
    rev(i, p) if(dep[i->to] == dep[p]+1 && i->val) {
        int tmp = dfs(i->to, min(mf-nf, i->val));
        if(!tmp) dep[i->to] = 0;
        nf += tmp;
        i->val -= tmp;
        i->back->val += tmp;
        if(nf == mf) break;
    }
    return nf;
}
int dinic() {
    int ret = 0;
    while(bfs()) ret += dfs(S, INF);
    return ret;
}
int main() {
    int n = rd(), m = rd(), sum = 0;
    for(int i = 1; i <= n ; i ++ ) Add_Edge(i, T, rd());
    for(int i = 1; i <= m ; i ++ ) {
        int u = rd(), v = rd(), w = rd();
        sum += w;
        Add_Edge(S, i+n, w);
        Add_Edge(i+n, u, INF);
        Add_Edge(i+n, v, INF);
    }
    printf("%d\n", sum-dinic());
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注