题解
感觉有难度的一道网络流
自己的网络流水平还是远远不够
一开始以为是费用流搞了半天,发现无法处理只有第一次有效的情况
于是看题解才知道就是个最大权闭合子图
由于每种东西都只有第一次有效
那么我们可以考虑把区间作为点建图
考虑最大权闭合子图的模型
选择区间((i,j))的贡献就一定要选择区间((i+1,j),(i,j-1))的贡献
所以我们就把区间((i,j))向((i+1,j),(i,j-1))连边
流量为INF
然后如果选择(i~j)这段连续区间的寿司的额外收益(d[i][j])是正的就由源点连流量为收益的边
否则就向汇点连边
只有(i==j)的区间才向每个寿司连边
然后每种寿司选c个的花费是(m*id^2+c*id)
也就是说每个种类的寿司只会被计算一次(m*id^2)
但是会被计算(c)次(id)
所以就对于每种寿司建一个点向终点连(m*id^2)的边表示选择这种寿司就一定会先花费这些钱
然后再对于每个寿司建一个点,向表示ta的种类的点连(INF)的边表示选择这个寿司就已经选择了这个种类的寿司,然后再向终点连流量为(id)的边表示选择这个寿司的费用
代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 105 ;
const int N = 13005 ;
const int INF = 1e9 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , m , num = 1 , hea[N] ;
int bel[M] , d[M][M] ;
int S , T , ans , cnt , idt[M][M] , dep[N] ;
struct E {
int nxt , to , dis ;
} edge[N * 10] ;
inline void add_edge(int from , int to , int dis) {
edge[++num].nxt = hea[from] ; edge[num].to = to ;
edge[num].dis = dis ; hea[from] = num ;
}
inline void Insert(int from , int to , int dis) {
add_edge(from , to , dis) ;
add_edge(to , from , 0) ;
}
inline bool bfs() {
queue < int > q ; q.push(S) ;
memset(dep , 0, sizeof(dep)) ; dep[S] = 1 ;
while(!q.empty()) {
int u = q.front() ; q.pop() ;
for(int i = hea[u] ; i ; i = edge[i].nxt) {
int v = edge[i].to ;
if(!dep[v] && edge[i].dis > 0) {
dep[v] = dep[u] + 1 ;
q.push(v) ;
if(v == T) return true ;
}
}
}
return dep[T] ;
}
int dfs(int u , int dis) {
if(u == T || !dis) return dis ;
int sum = 0 ;
for(int i = hea[u] ; i ; i = edge[i].nxt) {
int v = edge[i].to ;
if(dep[v] == dep[u] + 1 && edge[i].dis > 0) {
int diss = dfs(v , min(dis , edge[i].dis)) ;
if(diss > 0) {
edge[i].dis -= diss ; edge[i ^ 1].dis += diss ;
sum += diss ; dis -= diss ; if(!dis) break ;
}
}
}
if(!sum) dep[u] = -1 ;
return sum ;
}
inline int dinic() {
int tot = 0 ;
while(bfs())
tot += dfs(S , INF) ;
return tot ;
}
int main() {
n = read() ; m = read() ;
S = 0 ; T = 12500 ;
for(int i = 1 ; i <= n ; i ++) bel[i] = read() ;
for(int i = 1 ; i <= n ; i ++)
for(int j = i ; j <= n ; j ++)
d[i][j] = read() ;
for(int i = 1 ; i <= 1000 ; i ++)
Insert(n + i , T , m * i * i) ;
for(int i = 1 ; i <= n ; i ++){
Insert(i , n + bel[i] , INF) ;
Insert(i , T , bel[i]) ;
}
cnt = n + 1000 ;
for(int i = 1 ; i <= n ; i ++)
for(int j = i ; j <= n ; j ++)
idt[i][j] = ++ cnt ;
for(int i = 1 ; i <= n ; i ++) {
Insert(idt[i][i] , i , INF) ;
if(d[i][i] > 0) {
ans += d[i][i] ;
Insert(S , idt[i][i] , d[i][i]) ;
}
else Insert(idt[i][i] , T , -d[i][i]) ;
}
for(int i = 1 ; i <= n ; i ++)
for(int j = i + 1 ; j <= n ; j ++) {
Insert(idt[i][j] , idt[i][j - 1] , INF) ;
Insert(idt[i][j] , idt[i + 1][j] , INF) ;
if(d[i][j] > 0) {
ans += d[i][j] ;
Insert(S , idt[i][j] , d[i][j]) ;
}
else Insert(idt[i][j] , T , -d[i][j]) ;
}
ans -= dinic() ;
printf("%d
",ans) ;
return 0 ;
}