例题：
例题4（我连不上topcoder！）（还没对拍）
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long int ll; 4 typedef pair<int,int> pii; 5 namespace FLOW 6 { 7 const ll inf=1E15; 8 int S,T; 9 int size=1,head[1000005]; 10 struct edge 11 { 12 int to,next; 13 ll w; 14 }E[1000005]; 15 inline void addE(int u,int v,ll w) 16 { 17 E[++size].to=v; 18 E[size].next=head[u]; 19 E[size].w=w; 20 head[u]=size; 21 } 22 inline void add(int u,int v,ll w) 23 { 24 addE(u,v,w); 25 addE(v,u,0); 26 } 27 inline void init(int s,int t) 28 { 29 for(int i=2;i<=size;++i) 30 { 31 head[E[i].to]=0; 32 E[i].to=E[i].w=E[i].next=0; 33 } 34 size=1; 35 S=s,T=t; 36 } 37 int dfn[1000005]; 38 inline bool bfs() 39 { 40 for(int i=S;i<=T;++i) 41 dfn[i]=-1; 42 queue<int>Q; 43 dfn[S]=0; 44 Q.push(S); 45 while(!Q.empty()) 46 { 47 int u=Q.front(); 48 Q.pop(); 49 for(int i=head[u];i;i=E[i].next) 50 { 51 int v=E[i].to; 52 if(dfn[v]!=-1||E[i].w==0) 53 continue; 54 dfn[v]=dfn[u]+1; 55 Q.push(v); 56 } 57 } 58 return dfn[T]!=-1; 59 } 60 ll dfs(int u,ll up) 61 { 62 if(u==T) 63 return up; 64 ll s=0; 65 for(int i=head[u];i;i=E[i].next) 66 { 67 int v=E[i].to; 68 if(dfn[v]!=dfn[u]+1||E[i].w==0) 69 continue; 70 ll x=dfs(v,min(up-s,E[i].w)); 71 s+=x; 72 E[i].w-=x; 73 E[i^1].w+=x; 74 if(x==0) 75 dfn[v]=-1; 76 if(s==up) 77 break; 78 } 79 return s; 80 } 81 bool vis[1000005]; 82 vector<int>solve(vector<ll>V,vector<pii>EE) 83 { 84 init(0,V.size()+1); 85 // cout<<"FLOW "<<S<<" "<<T<<endl; 86 for(int i=0;i<V.size();++i) 87 { 88 ll x=V[i]; 89 // cout<<"?? "<<i+1<<" "<<x<<endl; 90 if(x>0) 91 add(S,i+1,x); 92 else 93 add(i+1,T,-x); 94 } 95 for(int i=0;i<EE.size();++i) 96 { 97 // cout<<"ADD "<<EE[i].first<<" "<<EE[i].second<<endl; 98 add(EE[i].first,EE[i].second,inf); 99 } 100 while(bfs()) 101 dfs(S,inf); 102 for(int i=S;i<=T;++i) 103 vis[i]=0; 104 queue<int>Q; 105 Q.push(S); 106 vis[S]=1; 107 while(!Q.empty()) 108 { 109 int u=Q.front(); 110 Q.pop(); 111 for(int i=head[u];i;i=E[i].next) 112 { 113 int v=E[i].to; 114 if(E[i].w==0||vis[v]) 115 continue; 116 Q.push(v); 117 vis[v]=1; 118 } 119 } 120 vector<int>D; 121 for(int i=head[S];i;i=E[i].next) 122 if(!vis[E[i].to]) 123 D.push_back(E[i].to); 124 // for(int i=S;i<=T;++i) 125 // cout<<vis[i]<<" ";cout<<endl; 126 for(int i=head[T];i;i=E[i].next) 127 if(!vis[E[i].to]) 128 D.push_back(E[i].to); 129 sort(D.begin(),D.end()); 130 return D; 131 } 132 } 133 int n,m; 134 struct pt 135 { 136 int x,y; 137 ll d,w; 138 }a[1005]; 139 bool yes[1005][1005]; 140 vector<int>E[1005],what[1005]; 141 vector<int>wait; 142 void dfs1(int u,int F,int s) 143 { 144 for(int i=1;i<=m;++i) 145 if(min(a[i].x,a[i].y)==min(u,s)&&max(a[i].x,a[i].y)==max(u,s)) 146 for(int j=0;j<wait.size();++j) 147 yes[wait[j]][i]=1; 148 for(int i=0;i<E[u].size();++i) 149 { 150 int v=E[u][i]; 151 if(v==F) 152 continue; 153 wait.push_back(what[u][i]); 154 dfs1(v,u,s); 155 wait.pop_back(); 156 } 157 } 158 inline void init1() 159 { 160 for(int i=1;i<=n;++i) 161 dfs1(i,0,i); 162 } 163 void dfs2(int u,int F,int s) 164 { 165 for(int i=1;i<=m;++i) 166 if(min(a[i].x,a[i].y)==min(u,s)&&max(a[i].x,a[i].y)==max(u,s)) 167 for(int j=0;j<wait.size();++j) 168 yes[i][wait[j]]=1; 169 for(int i=0;i<E[u].size();++i) 170 { 171 int v=E[u][i]; 172 if(v==F) 173 continue; 174 wait.push_back(what[u][i]); 175 dfs2(v,u,s); 176 wait.pop_back(); 177 } 178 } 179 inline void init2() 180 { 181 for(int i=1;i<=n;++i) 182 dfs2(i,0,i); 183 } 184 int ans[1005]; 185 void solve(vector<int>V,vector<int>D) 186 { 187 if(V.empty()) 188 return; 189 if(D.size()==1) 190 { 191 for(int i=0;i<V.size();++i) 192 ans[V[i]]=D[0]; 193 return; 194 } 195 assert(D.size()!=0); 196 int mid=(D.size()-1)/2; 197 ll x=D[mid],y=D[mid+1]; 198 vector<ll>V2; 199 vector<pii>E; 200 for(int i=0;i<V.size();++i) 201 for(int j=0;j<V.size();++j) 202 if(yes[V[i]][V[j]]) 203 E.push_back(pii(i+1,j+1)); 204 for(int i=0;i<V.size();++i) 205 { 206 // cout<<"?!?! "<<V[i]<<" "<<x<<" "<<y<<" "<<a[V[i]].d<<" "<<a[V[i]].w<<endl; 207 V2.push_back(-(abs(a[V[i]].d-y)-abs(a[V[i]].d-x))*a[V[i]].w); 208 } 209 vector<int>D2=FLOW::solve(V2,E); 210 // cout<<"NOW"<<endl; 211 // for(auto p:V) 212 // cout<<p<<" ";cout<<endl; 213 // for(auto p:D) 214 // cout<<p<<" ";cout<<endl; 215 // for(auto p:D2) 216 // cout<<p<<" ";cout<<endl; 217 // system("pause"); 218 vector<int>VL,VR,DL,DR; 219 int pos=0; 220 for(int i=0;i<V.size();++i) 221 { 222 if(pos!=D2.size()&&D2[pos]==V[i]) 223 { 224 VL.push_back(V[i]); 225 ++pos; 226 } 227 else 228 VR.push_back(V[i]); 229 } 230 for(int i=0;i<=mid;++i) 231 DL.push_back(D[i]); 232 for(int i=mid+1;i<D.size();++i) 233 DR.push_back(D[i]); 234 solve(VL,DL),solve(VR,DR); 235 } 236 int main() 237 { 238 ios::sync_with_stdio(false); 239 cin>>n>>m; 240 vector<int>V,D; 241 for(int i=1;i<=m;++i) 242 { 243 cin>>a[i].x>>a[i].y>>a[i].d>>a[i].w; 244 V.push_back(i); 245 D.push_back(a[i].d); 246 } 247 sort(D.begin(),D.end()); 248 unique(D.begin(),D.end()); 249 for(int i=2;i<=n;++i) 250 { 251 int x; 252 cin>>x; 253 E[a[x].x].push_back(a[x].y); 254 what[a[x].x].push_back(x); 255 E[a[x].y].push_back(a[x].x); 256 what[a[x].y].push_back(x); 257 } 258 init1(); 259 for(int i=1;i<=n;++i) 260 E[i].clear(),what[i].clear(); 261 for(int i=2;i<=n;++i) 262 { 263 int x; 264 cin>>x; 265 E[a[x].x].push_back(a[x].y); 266 what[a[x].x].push_back(x); 267 E[a[x].y].push_back(a[x].x); 268 what[a[x].y].push_back(x); 269 } 270 init2(); 271 // for(int i=1;i<=m;++i,cout<<endl) 272 // for(int j=1;j<=m;++j) 273 // cout<<yes[i][j]<<" ";cout<<endl; 274 solve(V,D); 275 ll sum=0; 276 for(int i=1;i<=m;++i) 277 sum+=abs(ans[i]-a[i].d)*a[i].w; 278 cout<<sum<<endl; 279 for(int i=1;i<=m;++i) 280 cout<<ans[i]<<endl; 281 return 0; 282 }
[USACO21JAN铂金] Minimum Cost Paths（luoguP7294）
我们形式化地计算一条路径的代价。我们记录第i列走到了第$s_i$行，那么走到(n,m)的总代价就是$\sum_{i=1}^{m-1}{(s_i-s_{i-1})*a_i+s_i^2}+(n-s_{m-1})*a_m$（计算相邻两列行数增加产生的贡献，以及除了最后一列列数增加产生的贡献），其中$s_0=1$，且$s_i\leqs_{i+1}$。
注意到$(s_i-\frac{a_{i+1}-a_i}{2})^2=s_i^2-s_i*a_{i+1}+s_i*a_i+(\frac{a_{i+1}-a_i}{2})^2$，令$c_i=\frac{a_{i+1}-a_i}{2}$，需要优化的式子变为：
$\sum_{i=1}^{m-1}{(s_i-c_i)^2}+C$（注意上标！），其中$C$是一个我们不需要关心的常数。至此，这变成了L2问题。
注意到问题特殊的拓扑关系，我们可以沿用论文中的例题1的方法。由于s得是整数，最后所有的s都四舍五入（并且这是正确的）。由于多组询问，我们得保证s小于等于每次询问的x，而m等于每次询问的y，因此我们离线将询问按照y从小到大排序依次处理，对于每次询问二分到栈上相应的位置计算相应的贡献即可。
注意s也是正整数！
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long int ll; 4 typedef long double ld; 5 const int maxn=2E5+5; 6 ll n,m,q,ans[maxn]; 7 ld a[maxn],c[maxn],sumA[maxn]; 8 int tot; 9 ld f[maxn],s[maxn]; 10 int L[maxn],R[maxn]; 11 struct query 12 { 13 int id,x,y; 14 bool operator<(const query&A)const 15 { 16 return y<A.y; 17 } 18 }Q[maxn]; 19 namespace BIT 20 { 21 ll t[maxn]; 22 inline int lowbit(int x) 23 { 24 return x&(-x); 25 } 26 inline ll ask(int x) 27 { 28 ll s=0; 29 while(x) 30 { 31 s+=t[x]; 32 x-=lowbit(x); 33 } 34 return s; 35 } 36 inline void add(int x,ll y) 37 { 38 while(x<=m) 39 { 40 t[x]+=y; 41 x+=lowbit(x); 42 } 43 } 44 } 45 inline void push(ld x,ld y,int l,int r) 46 { 47 f[++tot]=x; 48 s[tot]=y; 49 L[tot]=l; 50 R[tot]=r; 51 } 52 ll now=0; 53 inline ll get(int pos) 54 { 55 ll x=round(max((ld)1,f[pos])); 56 ll y=round(max((ld)1,f[pos-1])); 57 return (x-y)*a[L[pos]]+x*x*(R[pos]-L[pos]+1); 58 } 59 inline void update() 60 { 61 while(tot>=2&&f[tot-1]>f[tot]) 62 { 63 ld x=(s[tot-1]*f[tot-1]+s[tot]*f[tot])/(s[tot-1]+s[tot]),y=s[tot-1]+s[tot]; 64 int l=L[tot-1],r=R[tot]; 65 ld g=get(tot); 66 now-=g; 67 BIT::add(tot,-g); 68 69 g=get(tot-1); 70 now-=g; 71 BIT::add(tot-1,-g); 72 73 tot-=2; 74 push(x,y,l,r); 75 g=get(tot); 76 now+=g; 77 BIT::add(tot,g); 78 } 79 } 80 int b[maxn]; 81 int tmp[maxn]; 82 inline ll solve(ll x,ll y) 83 { 84 if(y==1) 85 return (x-1)*a[1]; 86 int l=1,r=tot,mid; 87 while(l<r) 88 { 89 mid=(l+r)>>1; 90 if(f[mid]<=x) 91 l=mid+1; 92 else 93 r=mid; 94 } 95 mid=l; 96 ll sum=BIT::ask(mid-1); 97 ll X=max((ll)1,(ll)round(min((ld)x,f[mid]))); 98 ll Y=max((ll)1,(ll)round(min((ld)x,f[mid-1]))); 99 sum+=a[L[mid]]*X-a[L[mid]]*Y+X*X*(y-1-L[mid]+1); 100 return sum+(x-X)*a[y]; 101 /* 102 for(int i=1;i<=tot;++i) 103 for(int j=L[i];j<=R[i];++j) 104 b[j]=min((int)round(max((ld)1,f[i])),x); 105 ll sum=0; 106 for(int i=1;i<=y-1;++i) 107 sum+=(ll)(b[i]-b[i-1])*a[i]+(ll)b[i]*b[i]; 108 return sum+(ll)(x-b[y-1])*a[y]; 109 */ 110 } 111 inline void solve() 112 { 113 f[0]=1; 114 sort(Q+1,Q+q+1); 115 int pos=1; 116 for(int i=1;i<=m-1;++i) 117 { 118 while(pos<=q&&Q[pos].y==i) 119 { 120 ans[Q[pos].id]=solve(Q[pos].x,Q[pos].y); 121 ++pos; 122 } 123 push(c[i],1,i,i); 124 ld g=get(tot); 125 now+=g; 126 BIT::add(tot,g); 127 update(); 128 } 129 while(pos<=q) 130 { 131 ans[Q[pos].id]=solve(Q[pos].x,Q[pos].y); 132 ++pos; 133 } 134 } 135 int main() 136 { 137 // freopen("a.in","r",stdin); 138 // freopen("a.out","w",stdout); 139 ios::sync_with_stdio(false); 140 cin>>n>>m; 141 for(int i=1;i<=m;++i) 142 { 143 cin>>a[i]; 144 sumA[i]=sumA[i-1]+a[i]; 145 } 146 for(int i=1;i<m;++i) 147 c[i]=(a[i+1]-a[i])/2; 148 cin>>q; 149 for(int i=1;i<=q;++i) 150 { 151 cin>>Q[i].x>>Q[i].y; 152 Q[i].id=i; 153 } 154 solve(); 155 for(int i=1;i<=q;++i) 156 cout<<ans[i]<<‘\n‘; 157 return 0; 158 }
原文：https://www.cnblogs.com/GreenDuck/p/14476886.html
