前言
这一个Task被神仙们吊着打。
Solution
考虑对于每一个(i,j)显然(i,j-1)和(i+1,j)都是要选的，然后连边。
再一看，最大权闭合子图？代码实现
#include#include #include #include #include #include #include using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=100010,Inf=1e9+10;int tot,a[110],k,n,m,v[110][110],id[110][110],cnt,front[100010],nxt[N<<3],to[N<<3],w[N<<3],s,t,dep[N],cur[N];void Add(int u,int v,int val){ to[cnt]=v;nxt[cnt]=front[u];front[u]=cnt;w[cnt]=val;cnt++;}bool bfs(){ queue Q;while(!Q.empty())Q.pop();memset(dep,0,sizeof(dep)); Q.push(s);dep[s]=1; while(!Q.empty()){ int u=Q.front();Q.pop(); for(int i=front[u];i!=-1;i=nxt[i]){ int v=to[i]; if(!dep[v] && w[i]){ dep[v]=dep[u]+1;Q.push(v); } } } return dep[t];}int dfs(int u,int Flow){ if(u==t || !Flow)return Flow; for(int &i=cur[u];i!=-1;i=nxt[i]){ int v=to[i]; if(dep[v]==dep[u]+1 && w[i]){ int di=dfs(v,min(Flow,w[i])); if(di){ w[i]-=di;w[i^1]+=di;return di; } else dep[v]=0; } } return 0;}int Dinic(){ int Flow=0; while(bfs()){ for(int i=s;i<=t;i++)cur[i]=front[i]; while(int d=dfs(s,Inf))Flow+=d; } return Flow;}int main(){ memset(front,-1,sizeof(front)); n=gi();m=gi();int tot=0; for(int i=1;i<=n;i++)a[i]=gi(),k=max(k,a[i]); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) v[i][j]=gi(),id[i][j]=++tot; s=0;t=tot+k+1; for(int i=1;i<=k;i++){Add(tot+i,t,m*i*i);Add(t,tot+i,m*i*i);} for(int i=1;i<=n;i++){Add(id[i][i],tot+a[i],Inf);Add(tot+a[i],id[i][i],0);v[i][i]-=a[i];} int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(v[i][j]>0){ans+=v[i][j];Add(s,id[i][j],v[i][j]);Add(id[i][j],s,0);} if(v[i][j]<0){Add(id[i][j],t,-v[i][j]);Add(t,id[i][j],0);} if(j>i){ Add(id[i][j],id[i][j-1],Inf);Add(id[i][j-1],id[i][j],0); Add(id[i][j],id[i+1][j],Inf);Add(id[i+1][j],id[i][j],0); } } printf("%d\n",ans-Dinic()); return 0;}