LOJ3097 SNOI2019 通信题解

费用流，当建边需要依靠位置和权值两个偏序关系时，可以用cdq分治优化建边。
代码：
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 20007
  4 #define M 200007
  5 const int inf=0x3f3f3f3f;
  6 #define ll long long
  7 struct flow
  8 {
  9     int hd[N],pre[M],to[M],num,w[M],mf[N],fa[N],maf,s,t;
 10     ll f[M],dis[N],ans;
 11     bool vis[N];
 12     queue<int> q;
 13     void adde(int x,int y,int z,int l)
 14         {
 15             num++;pre[num]=hd[x];hd[x]=num;to[num]=y;w[num]=z;f[num]=l;
 16             num++;pre[num]=hd[y];hd[y]=num;to[num]=x;w[num]=0;f[num]=-l;
 17         }
 18     void Init()
 19         {
 20             num=1;
 21         }
 22     bool spfa()
 23         {
 24             memset(dis,0x3f,sizeof(dis));
 25             memset(vis,0,sizeof(vis));
 26             while(!q.empty())q.pop();
 27             int i,v,u;
 28             dis[s]=0;
 29             mf[s]=inf;
 30             q.push(s);
 31             while(!q.empty())
 32             {
 33                 v=q.front();q.pop();
 34                 vis[v]=false;
 35                 for(i=hd[v];i;i=pre[i])
 36                 {
 37                     u=to[i];
 38                     if(w[i]&&dis[v]+f[i]<dis[u])
 39                     {
 40                         dis[u]=dis[v]+f[i];
 41                         fa[u]=i;
 42                         mf[u]=min(mf[v],w[i]);
 43                         if(!vis[u])
 44                         {
 45                             vis[u]=true;
 46                             q.push(u);
 47                         }
 48                     }
 49                 }
 50             }
 51             return dis[t]<1e18;
 52         }
 53     void update()
 54         {
 55             int v=t,i,fl=mf[t];
 56             while(v!=s)
 57             {
 58                 i=fa[v];
 59                 w[i]-=fl;
 60                 w[i^1]+=fl;
 61                 v=to[i^1];
 62             }
 63             ans+=dis[t]*fl;
 64             maf+=fl;
 65         }
 66     void main()
 67         {
 68             while(spfa())
 69                 update();
 70         }
 71 }D;
 72 struct str
 73 {
 74     int a,p;
 75 }p[N],tmp[N];
 76 bool operator <(str a,str b)
 77 {
 78     return a.p<b.p;
 79 }
 80 int tot,Pre[N],Suf[N],n;
 81 void cdq(int l,int r)
 82 {
 83     if(l==r)return;
 84     int mid=l+r>>1,i;
 85     cdq(l,mid),cdq(mid+1,r);
 86     for(i=l;i<mid;i++)
 87     {
 88         ++tot;
 89         Pre[i]=tot;
 90         D.adde(tot,p[i].p+n,inf,0);
 91         D.adde(tot+1,tot,inf,p[i+1].a-p[i].a);
 92     }
 93     ++tot;
 94     Pre[mid]=tot;
 95     D.adde(tot,p[mid].p+n,inf,0);
 96     for(i=mid;i>l;i--)
 97     {
 98         ++tot;
 99         Suf[i]=tot;
100         D.adde(tot,p[i].p+n,inf,0);
101         D.adde(tot+1,tot,inf,p[i].a-p[i-1].a);
102     }
103     ++tot;
104     Suf[l]=tot;
105     D.adde(tot,p[l].p+n,inf,0);
106     int j=l-1;
107     for(i=mid+1;i<=r;i++)
108     {
109         while(j<mid&&p[j+1].a<p[i].a)j++;
110         if(j>=l)D.adde(p[i].p,Pre[j],inf,p[i].a-p[j].a);
111         if(j<mid)D.adde(p[i].p,Suf[j+1],inf,p[j+1].a-p[i].a);
112     }
113     i=l,j=mid+1;
114     int k=l;
115     while(i<=mid&&j<=r)
116     {
117         if(p[i].a<p[j].a)
118             tmp[k++]=p[i++];
119         else tmp[k++]=p[j++];
120     }
121     while(i<=mid)tmp[k++]=p[i++];
122     while(j<=r)tmp[k++]=p[j++];
123     for(i=l;i<=r;i++)
124         p[i]=tmp[i];
125 }
126 int main()
127 {
128     int i,x,y,w;
129     scanf("%d%d",&n,&w);
130     for(i=1;i<=n;i++)
131     {
132         scanf("%d",&x);
133         p[i]={x,i};
134     }
135     D.Init();
136     D.s=2*n+1,D.t=2*n+2;
137     tot=2*n+2;
138     for(i=1;i<=n;i++)
139     {
140         D.adde(D.s,i,1,0);
141         D.adde(i,D.t,1,w);
142         D.adde(i+n,D.t,1,0);
143     }
144     sort(p+1,p+n+1);
145     cdq(1,n);
146     D.main();
147     printf("%lld
",D.ans);
148     return 0;
149 }
LOJ3097 SNOI2019 通信 题解

LOJ3097 SNOI2019 通信题解
