未完待续……
serve as网络流做题记录集&总结
1.CF1146G Zoning Restrictions
https://www.luogu.com.cn/problem/CF1146G
可能思路
- 转化为一个代价决策问题
即，考虑先把所有房子都建到h，然后再来决策是交罚金还是拆楼 - 有可能这类决策问题多采用↓的方法
- 凭空建立一条边(u,v)=+∞（本文中除非特殊说明(u,v)都从u到v）
- 选择元素i的代价为从源点到i建立一条边的权值
本题解法
那么首先是基于一个贪心思想：如果我们要交罚款，那肯定要建满房子。
于是就可以
- 对于每个房子，建立1~h这些点，表示一开始是建了这么高的
- 对每个决策建一个点，把[l,r]这一段的房子的[x+1~h]的点全部向这个点连权值为+∞的边
- 让这个点跟汇点连条权值为c的边
图解：（不要看白色线，画错了）
所以答案就是h*h*n-最小割。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N=2555,M=260000; //边要数清楚
int n,h,m,tot=1,dis[N],we[M];
vector<pair<int,int> >G[N];
queue<int>Q;
bool bfs(){
memset(dis,0,sizeof(dis));
Q.push(1),dis[1]=1;
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=0;i<G[x].size();i++){
int y=G[x][i].first,z=G[x][i].second;
if(we[z]&&!dis[y])dis[y]=dis[x]+1,Q.push(y);
}
}
return dis[2];
}
int dfs(int x,int in){
if(x==2)return in;
int out=0;
for(int i=0;i<G[x].size();i++){
int y=G[x][i].first,z=G[x][i].second;
if(we[z]&&dis[y]==dis[x]+1){
int los=dfs(y,min(in,we[z]));
we[z]-=los,we[z^1]+=los,in-=los,out+=los;
}
}
if(!out)dis[x]=-1;
return out;
}
void ade(int u,int v,int w){
G[u].push_back(make_pair(v,++tot)),we[tot]=w;
G[v].push_back(make_pair(u,++tot)),we[tot]=0;
}
int main(){
cin>>n>>h>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=h;j++)ade(1,2+(i-1)*h+j,2*j-1);
for(int i=1,l,r,x,c;i<=m;i++){
cin>>l>>r>>x>>c;
ade(2+n*h+i,2,c);
for(int j=l;j<=r;j++)for(int k=x+1;k<=h;k++)ade(2+(j-1)*h+k,2+n*h+i,1e9);
}
int ans=0;
while(bfs())ans+=dfs(1,1e9);
cout<<h*h*n-ans;
}