【BZOJ 1497】[NOI2006] 最大获利

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1497

解题报告

这题先考虑一种特别简单的建图方式：

考虑使用最小割来解决这个问题
将基站放在一边，客户放在另外一边
这样的话，我们不妨规定最后在S集的表示不选择，T集选择
考虑每一条增光路，必然要割掉客户到T的路径，或者基站到S的路径

酱紫的话，岂不是刚好满足条件？

当然使用以下这种经典的建图方式可以更优地建图：

Code

第一种建图方式：

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 55000+9;
const int M = N + 100000 << 1;
const int INF = 1e9;

int n,m,S,T,vout,head[N],nxt[M],to[M],flow[M];

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

inline void Add_Edge(int u, int v, int f = INF) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class Network_Flow{
    int cur[N],dis[N];
    queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur, head, sizeof(head));
                ret += DFS(S, INF);
            }   
            return ret;
        }
    private:
        inline bool BFS() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
             
            while (!que.empty()) {
                int w = que.front(); que.pop();
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > INF && flow[i]) {
                        dis[to[i]] = dis[w] + 1;
                        que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
        int DFS(int w, int f) {
            if (w == T) return f;
            else {
                int ret = 0;
                for (int tmp,&i=cur[w];i;i=nxt[i]) {
                    if (dis[to[i]] == dis[w] + 1 && flow[i]) {
                        tmp = DFS(to[i], min(f, flow[i])); 
                        flow[i] -= tmp; flow[i^1] += tmp;
                        f -= tmp; ret += tmp;
                        if (!f) break;
                    }
                }
                return ret;
            }
        }
}Dinic;

int main() {
	n = read(); m = read();
	S = 0; T = N - 1;
	for (int i=1;i<=n;i++)
		Add_Edge(S, i, read());
	for (int i=1,t;i<=m;i++) {
		Add_Edge(read(), i+n);
		Add_Edge(read(), i+n);
		vout += (t = read());
		Add_Edge(i+n, T, t);
	}
	printf("%d\n",vout-Dinic.MaxFlow());
	return 0;
}

第二种建图方式：

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000 + 9;
const int M = 100000 << 1;
const int INF = 1e9;

int n,m,S,T,vout,tmp[N],head[N],nxt[M],to[M],flow[M];

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

inline void Add_Edge(int u, int v, int f = INF, int t = 0) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = f * t;
}

class Network_Flow{
    int cur[N],dis[N];
    queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur, head, sizeof(head));
                ret += DFS(S, INF);
            }   
            return ret;
        }
    private:
        inline bool BFS() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
             
            while (!que.empty()) {
                int w = que.front(); que.pop();
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > INF && flow[i]) {
                        dis[to[i]] = dis[w] + 1;
                        que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
        int DFS(int w, int f) {
            if (w == T) return f;
            else {
                int ret = 0;
                for (int tmp,&i=cur[w];i;i=nxt[i]) {
                    if (dis[to[i]] == dis[w] + 1 && flow[i]) {
                        tmp = DFS(to[i], min(f, flow[i])); 
                        flow[i] -= tmp; flow[i^1] += tmp;
                        f -= tmp; ret += tmp;
                        if (!f) break;
                    }
                }
                return ret;
            }
        }
}Dinic;

int main() {
	n = read(); m = read();
	S = 0; T = N - 1;
	for (int i=1;i<=n;i++)
		Add_Edge(i, T, read() << 1);
	for (int i=1,t,x,y;i<=m;i++) {
		x = read(); y = read();
		vout += (t = read()) * 2;
		tmp[x] += t; tmp[y] += t;
		Add_Edge(x, y, t, 1);
	}
	for (int i=1;i<=n;i++) 
		Add_Edge(S, i, tmp[i]);
	printf("%d\n",vout-Dinic.MaxFlow()>>1);
	return 0;
}