Posted by 题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=4873
题解
最大权闭合子图，源点向所有权值为正的区间\([i,j]\)连边，容量为\(d[i][j]\)，所有权值为负的区间\([i,j]\)向汇点连边，容量为\(-d[i][j]\)；
所有表示代号的节点\(x\)向汇点连边，容量为\(mx^2\)，所有区间\([i,i]\)向表示该点代号的节点连边，容量为\(INF\)，所有区间\([i,i]\)向汇点连边，容量为该点的代号\(x\)；
最后，由于选择了\([i,j]\)就一定选择了\([i+1,j]\)和\([i,j-1]\)，故所有\(i < j\)的区间\([i,j]\)向区间\([i+1,j],[i,j-1]\)连边，容量为\(INF\)；
代码
|
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 101 102 103 104 105 106 107 108 109 110 111 |
#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; typedef long long LL; typedef double db; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); } return x*f; } const int MAXN=110; int n,m,sum,head[MAXN*MAXN],cnt,tot,ID[MAXN][MAXN],mp[1010]; struct edge { int v,next,val; }e[MAXN*MAXN*MAXN]; void addedge(int x,int y,int z) { e[cnt]=(edge){y,head[x],z}; head[x]=cnt++; swap(x,y); e[cnt]=(edge){y,head[x],0}; head[x]=cnt++; return; } struct MF { int idx[MAXN*MAXN],S,T,cur[MAXN*MAXN]; void bfs() { memset(idx,0,sizeof(idx)); queue<int>q; q.push(S); idx[S]=1; while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(!e[i].val||idx[v])continue; idx[v]=idx[u]+1; q.push(v); } } return; } int dfs(int u,int _min) { if(u==T)return _min; int ret=0,k; for(int i=cur[u];~i;i=e[i].next) { int v=e[i].v; cur[u]=i; if(!e[i].val||idx[v]!=idx[u]+1)continue; k=dfs(v,min(_min-ret,e[i].val)); e[i].val-=k; e[i^1].val+=k; ret+=k; if(ret==_min)break; } return ret; } int dinic() { int ret=0; while(true) { bfs(); if(!idx[T])break; memcpy(cur,head,sizeof(head)); ret+=dfs(S,INF); } return ret; } }T1; int main() { #ifndef ONLINE_JUDGE freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif n=read();m=read(); memset(head,-1,sizeof(head)); int S=0,T=n+n*(n+1)/2+1; int tot=n; for(int i=1;i<=n;++i) { int x=read(); if(!mp[x])mp[x]=++tot,addedge(tot,T,m*x*x); addedge(i,mp[x],INF);addedge(i,T,x); } for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) ID[i][j]=i==j?i:++tot; for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) { int x=read(); if(i!=j)addedge(ID[i][j],ID[i+1][j],INF),addedge(ID[i][j],ID[i][j-1],INF); if(x>0)addedge(S,ID[i][j],x),sum+=x; else addedge(ID[i][j],T,-x); } T1.S=S;T1.T=T; printf("%d\n",sum-T1.dinic()); return 0; } |