[atARC129E]Yet Another Minimization

考虑最小割，具体建图如下——

对变量$x_{i}$建立$m-1$个点，依次记作$V_{i,1},V_{i,2},...,V_{i,m-1}$，并定义$V_{i,0}=S,V_{i,m}=T$

再建立$m$条边，第$j$条边为$(V_{i,j-1},V_{i,j},C_{i,j})$，割掉即表示选$A_{i,j}$作为$x_{i}$

关于$|x_{i}-x_{j}|W_{i,j}$，实际上可以看作
$$
\sum_{a\in Z,x_{j}\le a,a+1\le x_{i}}W_{i,j}+\sum_{a\in Z,x_{i}\le a,a+1\le x_{j}}W_{i,j}
$$
将左式用$V_{i,*}$向$V_{j,*}$的边处理，根据对称性右式即会被$V_{j,*}$向$V_{i,*}$的边处理

具体的，即要求$\forall a\in Z,V_{i,*}$向$V_{j,*}$连一条边，使得恰仅有在$A_{j,y}\le a,a+1\le A_{i,x}$时需要再割掉这条边，那么显然从$V_{i,\min_{a+1\le A_{i,x}}x-1}$向$V_{j,\max_{A_{j,y}\le a}j}$连边权为$W_{i,j}$的边即可

将同一个点对间的边合并，显然$V_{i,x-1}$向$V_{j,y}$连的边边权和即
$$
\sum_{a\in Z,a+1\le A_{i,x},a\ge A_{i,x-1},A_{j,y}\le a,A_{j,y+1}\ge a+1}W_{i,j}=\max\{\min(A_{i,x},A_{j,y+1})-\max(A_{i,x-1},A_{j,y}),0\}W_{i,j}
$$
（特别的，不妨假设$A_{i,0}=0$且$A_{j,y}=\infty$）

此时，对同一个$i$可能割掉多条$(V_{i,j-1},V_{i,j})$的边，这只需将$C_{i,j}$再加上一个足够大量即可避免

（但事实上，不加反而能够通过，似乎是数据有一些问题？）

另外，显然上式对同一个$(i,j)$至多有$o(m)$条边权非0的边，因此总边数是$o(n^{2}m)$的

时间复杂度为$o(maxFlow(nm,n^{2}m))$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 55
 4 #define M 10
 5 #define maxV 305
 6 #define maxE 200005
 7 #define ll long long
 8 struct Edge{
 9     int nex,to;
10     ll len;
11 }edge[maxE];
12 queue<int>q;
13 int n,m,S,T,E,id[N][M],a[N][M],head[maxV],work[maxV],d[maxV];
14 ll w;
15 void add(int x,int y,ll z){
16     edge[E]=Edge{head[x],y,z};
17     head[x]=E++;
18     if (E&1)add(y,x,0);
19 }
20 bool bfs(){
21     memset(d,-1,sizeof(d));
22     d[S]=0,q.push(S);
23     while (!q.empty()){
24         int k=q.front();
25         q.pop();
26         for(int i=head[k];i!=-1;i=edge[i].nex)
27             if ((edge[i].len)&&(d[edge[i].to]<0)){
28                 d[edge[i].to]=d[k]+1;
29                 q.push(edge[i].to);
30             }
31     }
32     return d[T]>=0;
33 }
34 ll dfs(int k,ll s){
35     if (k==T)return s;
36     ll ans=0;
37     for(int &i=head[k];i!=-1;i=edge[i].nex)
38         if ((edge[i].len)&&(d[edge[i].to]==d[k]+1)){
39             ll p=dfs(edge[i].to,min(s,edge[i].len));
40             edge[i].len-=p,edge[i^1].len+=p,s-=p,ans+=p;
41             if (!s)return ans;
42         }
43     return ans;
44 }
45 ll dinic(){
46     ll ans=0;
47     memcpy(work,head,sizeof(head));
48     while (bfs()){
49         ans+=dfs(S,1e18); 
50         memcpy(head,work,sizeof(head));
51     }
52     return ans;
53 }
54 int main(){
55     scanf("%d%d",&n,&m),S=0,T=n*(m-1)+1;
56     memset(head,-1,sizeof(head));
57     for(int i=1;i<=n;i++){
58         id[i][0]=S,id[i][m]=T;
59         for(int j=1;j1)*(m-1)+j;
60         for(int j=1;j<=m;j++){
61             scanf("%d%lld",&a[i][j],&w);
62             add(id[i][j-1],id[i][j],w);
63         }
64         a[i][m+1]=1e6;
65     }
66     for(int i=1;i<=n;i++)
67         for(int j=i+1;j<=n;j++){
68             scanf("%lld",&w);
69             for(int x=1;x<=m;x++)
70                 for(int y=1;y<=m;y++){
71                     add(id[i][x-1],id[j][y],max(min(a[i][x],a[j][y+1])-max(a[i][x-1],a[j][y]),0)*w);
72                     add(id[j][x-1],id[i][y],max(min(a[j][x],a[i][y+1])-max(a[j][x-1],a[i][y]),0)*w);
73                 }
74         }
75     printf("%lld\n",dinic());
76     return 0;
77 }