BZOJ4873 [Shoi2017]寿司餐厅 【最大权闭合子图】

题目链接

BZOJ4873

题解

题意很鬼畜，就可以考虑网络流【雾】

然后就会发现这是一个裸的最大权闭合子图

就是注意要离散化一下代号

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 11005,maxm = 8000005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

int h[maxn],ne = 1;

struct EDGE{int to,nxt,f;}ed[maxm];

inline void build(int u,int v,int f){

	ed[++ne] = (EDGE){v,h[u],f}; h[u] = ne;

	ed[++ne] = (EDGE){u,h[v],0}; h[v] = ne;

}

int cur[maxn],vis[maxn],used[maxn],d[maxn],now,S,T;

int q[maxn],head,tail;

inline bool bfs(){

	q[head = tail = 0] = S; vis[S] = now; d[S] = 0;

	int u;

	while (head <= tail){

		u = q[head++];

		Redge(u) if (ed[k].f && vis[to = ed[k].to] != now){

			d[to] = d[u] + 1; vis[to] = now;

			if (to == T) return true;

			q[++tail] = to;

		}

	}

	return vis[T] == now;

}

int dfs(int u,int minf){

	if (u == T || !minf) return minf;

	int flow = 0,f,to;

	if (used[u] != now) cur[u] = h[u],used[u] = now;

	for (int& k = cur[u]; k; k = ed[k].nxt)

		if (vis[to = ed[k].to] == now && d[to] == d[u] + 1 && (f = dfs(to,min(minf,ed[k].f)))){

			ed[k].f -= f; ed[k ^ 1].f += f;

			flow += f; minf -= f;

			if (!minf) break;

		}

	return flow;

}

int maxflow(){

	int flow = 0; now = 1;

	while (bfs()){

		flow += dfs(S,INF);

		now++;

	}

	return flow;

}

int n,m,w[105][105],x[105],b[maxn],tot,id[105][105],cnt,ans;

int main(){

	n = read(); m = read(); S = 0;

	REP(i,n) b[i] = x[i] = read();

	sort(b + 1,b + 1 + n); tot = 1;

	for (int i = 2; i <= n; i++) if (b[i] != b[tot]) b[++tot] = b[i];

	for (int i = 1; i <= n; i++) x[i] = lower_bound(b + 1,b + 1 + tot,x[i]) - b;

	cnt = n + tot;

	for (int i = 1; i <= n; i++){

		for (int j = i; j <= n; j++){

			id[i][j] = ++cnt;

			w[i][j] = read();

		}

	}

	T = ++cnt;

	REP(i,n){

		build(i,x[i] + n,INF);

		build(i,T,b[x[i]]);

	}

	REP(i,tot) build(i + n,T,m * b[i] * b[i]);

	for (int i = 1; i <= n; i++){

		for (int j = i; j <= n; j++){

			if (w[i][j] >= 0) build(S,id[i][j],w[i][j]),ans += w[i][j];

			else build(id[i][j],T,-w[i][j]);

			for (int k = i; k <= j; k++)

				build(id[i][j],k,INF);

			if (i < j){

				build(id[i][j],id[i + 1][j],INF);

				build(id[i][j],id[i][j - 1],INF);

			}

		}

	}

	printf("%d\n",ans - maxflow());

	return 0;

}