• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[atARC129E]Yet Another Minimization

开发技术 开发技术 1周前 (11-24) 6次浏览

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

对变量$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_{ain Z,x_{j}le a,a+1le x_{i}}W_{i,j}+sum_{ain Z,x_{i}le a,a+1le x_{j}}W_{i,j}
$$
将左式用$V_{i,*}$向$V_{j,*}$的边处理,根据对称性右式即会被$V_{j,*}$向$V_{i,*}$的边处理

具体的,即要求$forall ain Z,V_{i,*}$向$V_{j,*}$连一条边,使得恰仅有在$A_{j,y}le a,a+1le A_{i,x}$时需要再割掉这条边,那么显然从$V_{i,min_{a+1le 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_{ain Z,a+1le A_{i,x},age 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))$,可以通过

[atARC129E]Yet Another Minimization[atARC129E]Yet Another Minimization

 1 #include<bits/stdc++.h>
 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;j<m;j++)id[i][j]=(i-1)*(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("%lldn",dinic());
76     return 0;
77 }

View Code

 


程序员灯塔
转载请注明原文链接:[atARC129E]Yet Another Minimization
喜欢 (0)