bzoj4873-最大权闭合子图

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<string>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<iomanip>
  8 #include<queue>
  9 using namespace std;
 10 namespace Moxing {
 11     const int N=105,M=1005;
 12     const int inf=0x3f3f3f3f;
 13     int n,m,a[N],mp[N][N],id[N][N],idw[M],ict,S,T,cnt=1,last[30303];
 14     long long sum;
 15     bool vis[M];
 16     struct node {
 17         int to,dis,nxt;
 18     } edge[30303<<6];
 19     void add(int from,int to,int dis) {
 20         edge[++cnt].to=to,edge[cnt].dis=dis,edge[cnt].nxt=last[from],last[from]=cnt;
 21         //    edge[++cnt].to=from,edge[cnt].dis=dis,edge[cnt].nxt=last[from],last[from]=cnt;
 22     }
 23     void insert(int from,int to,int dis) {
 24         add(from,to,dis),add(to,from,0);
 25     //    cout<<from<<‘ ‘<<to<<‘ ‘<<dis<<endl;
 26     }
 27     void build() {
 28         for(int i=1; i<=n; i++) {
 29             for(int j=i; j<=n; j++) {
 30                 id[i][j]=++ict;
 31             }
 32         }
 33         for(int i=1; i<=n; i++) {
 34             if(vis[a[i]]) continue ;
 35             vis[a[i]]=1,idw[a[i]]=++ict;
 36         }
 37         //    memset(vis,0,sizeof(vis));
 38         S=0,T=ict+n+1;
 39         for(int i=1; i<=n; i++) {
 40             for(int j=i; j<=n; j++) {
 41                 if(mp[i][j]>0) {//1
 42                     insert(S,id[i][j],mp[i][j]);//cout<<‘1‘<<‘ ‘;
 43                 } else if(mp[i][j]<0) {
 44                     insert(id[i][j],T,-mp[i][j]);//cout<<‘1‘<<‘ ‘;
 45                 }
 46                 insert(id[i][j],ict+i,inf);//2
 47                 insert(id[i][j],ict+j,inf);//cout<<‘2‘<<‘ ‘;
 48                 if(i!=j) { //5
 49                     insert(id[i][j],id[i+1][j],inf);
 50                     insert(id[i][j],id[i][j-1],inf);//cout<<‘5‘<<‘ ‘;
 51                 }
 52             }
 53         }
 54         memset(vis,0,sizeof(vis));
 55         for(int i=1; i<=n; i++) {
 56             if(vis[a[i]]) continue ;
 57             vis[a[i]]=1,insert(idw[a[i]],T,m*a[i]*a[i]);//cout<<‘3‘<<‘ ‘;//3
 58         }
 59         for(int i=1; i<=n; i++) {
 60             insert(ict+i,idw[a[i]],inf);//4
 61             insert(ict+i,T,a[i]);//cout<<‘4‘<<‘ ‘;
 62         //    cout<<"Moxing"; 
 63         }
 64         //    cout<<endl;
 65         return ;
 66     }
 67     int d[M*10];
 68     bool bfs() {
 69         memset(d,0,sizeof(d));
 70         queue<int>q;
 71         d[S]=1;
 72         q.push(S);
 73         while(!q.empty()) {
 74             int x=q.front();
 75             q.pop();
 76             for(int i=last[x]; i; i=edge[i].nxt) {
 77                 int y=edge[i].to;
 78                 if(!d[y] && edge[i].dis) {
 79                     d[y]=d[x]+1;
 80                     q.push(y);
 81                     //cout<<y<<‘ ‘;
 82                 }
 83             }
 84         }
 85         //cout<<d[T]<<‘ ‘;
 86         return d[T];
 87     }
 88     int dfs(int x,int lim) {
 89         if(x==T) return lim;
 90         int f=0,tmp;
 91         for(int i=last[x]; i; i=edge[i].nxt) {
 92             int y=edge[i].to;
 93             if(d[y]==d[x]+1&&edge[i].dis&&(tmp=dfs(y,min(lim,edge[i].dis)))) {
 94                 edge[i].dis-=tmp,edge[i^1].dis+=tmp;
 95                 lim-=tmp;
 96                 f+=tmp;
 97                 if(!lim) return f;
 98             }
 99         }
100         d[x]=0;
101         return f;
102     }
103     long long dinic() {
104         long long res=0;
105         //    cout<<dfs(S,inf)<<‘ ‘;
106         while(bfs()) res+=dfs(S,inf);
107         return res;
108     }
109     struct main {
110         main() {
111             scanf("%d%d",&n,&m);
112             for(int i=1; i<=n; i++) {
113                 scanf("%d",&a[i]);
114             }
115             for(int i=1; i<=n; i++) {
116                 for(int j=i; j<=n; j++) {
117                     scanf("%d",&mp[i][j]);
118                     if(mp[i][j]>0) sum+=mp[i][j];
119                 }
120             }
121             build();
122             long long res=dinic();
123             //    printf("%lld\n",res);
124             sum-=res;
125             printf("%lld\n",sum);
126             exit(0);
127         }
128     } UniversalLove;
129 }
130 int main() {
131     Moxing::main();
132 }