Solve

NOI2006最大获利-最大权闭合子图

题目解答

首先按照题目要求先建立二分图：左边是用户点，右边是通讯站，并给他们附上权值为正无穷。然后右边的点向超级汇连边，权值为中转站的花费。超级源向左边的点连边，权值是获利。然后求出最大流。这个最大流的含义是：因为最大流 = 最小割。中间部分的边容量是正无穷不会被割开，而只会割开源与汇的边，也就是（不打算纳入获利的值 + 建一部分通讯站的费用），因为是最小割，所以保证这样的耗费最小，也就是说这是我们不需要的值。因此最终结果是：可获利的总权值 -最大流。

运行情况

NOI 2006 - 最大获利

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstring>
#include<climits>
#define BIG 400005
#define MAX 99999999

using namespace std;
struct edge{
    int x,y,cap;
    edge *next,*target;
    edge(){}
    edge(int x,int y,int cap,edge *next):x(x),y(y),cap(cap),next(next),target(0){}
    void *operator new(size_t,void *ptr){return ptr;}
}*EDGE[BIG];

long source=BIG-2,sink=BIG-1,queue[BIG],Dist[BIG],n,m,MAXTOT;
edge *Stack[BIG],*Path[BIG];
inline bool LabelFlowDist(){
    long tail=1,head=0,now;
    memset(Dist,-1,sizeof(Dist));
    Dist[source]=0;
    queue[tail]=source;
    while(head<tail){
        now=queue[++head];
        for(edge *e=EDGE[now];e;e=e->next)
        if(e->cap!=0 && Dist[e->y]==-1){
            Dist[e->y]=Dist[e->x]+1;
            queue[++tail]=e->y;
            if(e->y==sink) return 1;
        }
    }
    return 0;
}

inline void FindMaxFlow(){
    long top=source,record,delta,Lpath=1;
    memcpy(Stack,EDGE,sizeof(EDGE));
    while(top>0){
        if(sink==top){
            delta=INT_MAX;
            for(int i=1;i<Lpath;i++)
            if(delta>Path[i]->cap){
                delta=Path[i]->cap;
                record=i;
            }
            for(int i=1;i<Lpath;i++){
                Path[i]->cap-=delta;
                Path[i]->target->cap+=delta;
            }
            Lpath=record;
            top=Path[Lpath]->x;
            MAXTOT+=delta;
        }
        edge *temE;
        for(temE=Stack[top];temE;temE=temE->next)
            if(temE->cap!=0 && Dist[temE->y]==Dist[top]+1) break;
        Stack[top]=temE;
        if(temE){
            Path[Lpath++]=temE;
            top=temE->y;
        }else{
            Dist[top]=-1;
            if(Lpath==1) return ;
            top=Path[--Lpath]->x;
        }
    }
}

int main(){
    cin>>n>>m;
    long A,B,num,TOTAL=0,M;
    edge *tempEDGE=new edge[BIG*2];
    for(int i=1;i<=n;i++){
        cin>>num;
        EDGE[i]=new((void*)tempEDGE++) edge(i,sink,num,EDGE[i]);
        EDGE[sink]=new((void*)tempEDGE++) edge(sink,i,0,EDGE[sink]);
        EDGE[i]->target=EDGE[sink];
        EDGE[sink]->target=EDGE[i];
    }
    for(int i=1;i<=m;i++){
        cin>>A>>B>>num;
        TOTAL+=num;
        M=i+n;
        EDGE[source]=new((void*)tempEDGE++) edge(source,M,num,EDGE[source]);
        EDGE[M]=new((void*)tempEDGE++) edge(M,source,0,EDGE[M]);
        EDGE[M]->target=EDGE[source];
        EDGE[source]->target=EDGE[M];
        EDGE[M]=new((void*)tempEDGE++) edge(M,A,MAX,EDGE[M]);
        EDGE[A]=new((void*)tempEDGE++) edge(A,M,0,EDGE[A]);
        EDGE[M]->target=EDGE[A];
        EDGE[A]->target=EDGE[M];
        EDGE[M]=new((void*)tempEDGE++) edge(M,B,MAX,EDGE[M]);
        EDGE[B]=new((void*)tempEDGE++) edge(B,M,0,EDGE[B]);
        EDGE[M]->target=EDGE[B];
        EDGE[B]->target=EDGE[M];
    }
    while(LabelFlowDist()) FindMaxFlow();
    cout<<TOTAL-MAXTOT<< endl;
    return 0;
}

难易等级

Middle Up(NOI)