2022/2/5

2022/2/5

[P1361 小M的作物]( P1361 小M的作物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) )

最大流最小割

划分集合关系,求最小割

建模方法:

  1. 将作物i与源点s连一条流量为a[i]的边,s->i。代表这个作物种在A的收益
  2. 将作物i与汇点t连一条流量为b[i]的边,i->t。代表这个作物种在B的收益
  3. 考虑组合,建立虚点 \(c\),源点s连向\(c\),流量为\(c_{1,i}\),\(c\)连向组合中的作物,流量为inf,保证这条边不会被割,\(c_{2,i}\)同理。

建出来的图如下

2022/2/5

在此图跑一边网络流,求出最小割,割去的边是不需要的,那么总的收益减去最小割,就是答案。

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)

#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}

const int qs=4e6+7;
const ll mod=998244353;
const ll inf=0x3f3f3f3f;

ll a[qs],b[qs],n,m,num,sum,s,t;

ll head[qs],nxt[qs],to[qs],dis[qs],p;

void add(int fx,int tx,ll dx){
	to[p]=tx; dis[p]=dx; nxt[p]=head[fx]; head[fx]=p++;
    //反向边 
	to[p]=fx; dis[p]=0; nxt[p]=head[tx]; head[tx]=p++;
}

void build_map(){
	memset(head,-1,sizeof(head));
	s=0,t=n+1;num=t+1;
	for(int i=1;i<=n;++i) add(s,i,a[i]);
	for(int i=1;i<=n;++i) add(i,t,b[i]);
	m=read();
	ll c1,c2,k,x;
	for(int i=1;i<=m;++i){
		k=read(),c1=read(),c2=read();
		sum=sum+c1+c2;
		add(s,num,c1); num++;
		add(num,t,c2); num++;
		for(int j=1;j<=k;++j){
			x=read();
			add(num-2,x,inf);
			add(x,num-1,inf);
		}
	}
}
//Dinic
ll level[qs],cur[qs];
//level是各点到终点的深度,cur为当前弧优化的增广起点 
bool bfs(){//分层图 
	memset(level,-1,sizeof(level));
	level[s]=0;
	memcpy(cur,head,sizeof(head));
	cur[s]=head[s];
	queue<int> Q;
	Q.push(s);
	while(Q.si){
		int k=Q.front();
		Q.pop();
		for(int i=head[k];i!=-1;i=nxt[i]){
			if(dis[i]>0&&level[to[i]]==-1){
				level[to[i]]=level[k]+1;
				Q.push(to[i]);
				if(to[i]==t) return true;
			}
		}
	}
	return false;
}
ll dfs(int u,ll flow){
	if(u==t) return flow;
	
	ll ret=flow; //剩余的流量
	for(int i=cur[u];i!=-1&&ret>0;i=nxt[i]){
		cur[u]=i;// 当前弧优化
		//如果还能流下去 并且 更深 
		if(dis[i]>0&&level[to[i]]==level[u]+1){
			ll c=dfs(to[i],min(dis[i],ret));
			if(!c) level[to[i]]=-1; //剪枝,出去增广完毕的点 
			ret-=c; //剩余的水流被用了c
			dis[i]-=c;	//减权重 
			dis[i^1]+=c; //反向边加权重 
		}
	} 
	return flow-ret;//返回用掉的水流 
}
//END 


int main(){
	n=read();
	sum=0;
	for(int i=1;i<=n;++i) a[i]=read(),sum+=a[i];
	for(int i=1;i<=n;++i) b[i]=read(),sum+=b[i];
	build_map();
	ll ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	cout<<sum-ans<<"\n";
	
	return 0;
}

[ 炮兵阵地 ]( 炮兵阵地 (nowcoder.com) )

状压dp

(好像是第3次写这道题了,之前都是半懵半懂的写,不过这次思路清晰多了。

\(f[i][j][k]\)表示第i行状态为j,第i-1行状态为k的最大炮兵数量。

状态转移方程为\(f[i][j][k]=max(f[i][j][k],f[i-1][k][k1]+count[i])\)

\(count[i]\)表示状态i的二进制中1的数量

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)

#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}

const int qs=107;
const ll mod=998244353;
const ll inf=0x3f3f3f3f;


int n,m,sta[qs],cnt,s_1[qs],val[qs]; 
int f[qs][qs][qs]; //f[i][j][k]表示第i行状态为j,第i-1行状态为k的炮兵数 
char c[qs][qs];

int get_sum(int x){
	int ret=0;
	while(x){
		if(x&1) ret++;
		x>>=1;
	}
	return ret;
}
int ans=0;
void pre(){
	cnt=0;
	for(int i=0;i<(1<<m);++i){
		//预处理出所有可行状态 
		if((i&(i<<1)) || (i&(i<<2)) ) continue;
		sta[++cnt]=i;
		s_1[cnt]=get_sum(i);
	}
	for(int i=1;i<=n;++i){
		int v=0;
		for(int j=m,k=0;j>=1;--j,++k){
			if(c[i][j]=='P') continue;
			v+=(1<<k);
		}
		//处理出每行的二进制数,p代表1,h代表0 
		val[i]=v;
	}
	//与处理出第1行的状态 
	for(int i=1;i<=cnt;++i){
		for(int j=1;j<=cnt;++j){
			if(val[1]&sta[i]) continue;
			f[1][i][j]=s_1[i];
			ans=max(ans,s_1[i]);
		}
	}
	
}

void dp(){
	
	for(int fi=2;fi<=n;++fi){
		for(int i=1;i<=cnt;++i){//当前行状态 
			if(sta[i]&val[fi]) continue;//状态与H冲突
			for(int j=1;j<=cnt;++j){//fi-1行状态 
				if((sta[j]&val[fi-1])||(sta[i]&sta[j]))continue;//同上
				for(int k=1;k<=cnt;++k) {//fi-2行状态 
					if((sta[k]&val[fi-2])||(sta[i]&sta[k])||(sta[j]&sta[k])) continue;
					f[fi][i][j]=max(f[fi][i][j],f[fi-1][j][k]+s_1[i]);
					ans=max(ans,f[fi][i][j]);
				}
			}
		}
	
	}
	cout<<ans<<"\n";
}


int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) cin>>c[i]+1;
	pre();
	dp();
	return 0;
}

[ [SCOI2005]互不侵犯KING ]( [SCOI2005]互不侵犯KING (nowcoder.com) )

状压dp

\(f[i][j][k]表示第i行状态为j,且已经放了k个国王的方案数。\)

状态转移方程为:\(f[i][j][k]+=f[i-1][j1][k-count[j]]\)

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define se second
#define pb push_back
#define pf push_front
#define si size()
#define db double
#define ls (p<<1)
#define rs (p<<1|1)

#define fi first
#define se second
using namespace std;
ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(ll x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}

const int qs=107;
const ll mod=998244353;
const ll inf=0x3f3f3f3f;

ll n,m,sta[600],cnt,cnt_1[600];
ll f[11][600][100]; //f[i][j][k]表示第i行状态为j,且已经放了k个国王的方案数。 


int get_sum(int x){
	ll ret=0;
	while(x){
		if(x&1) ret++;
		x>>=1;
	}
	return ret;
}

void pre(){
	cnt=0;
	for(int i=0;i<(1<<n);++i){
		if((i&(i<<1))||(i&(i>>1))) continue;
		sta[++cnt]=i;
		cnt_1[cnt]=get_sum(i);
	}
}

void dp(){
	ll ans=0;
	for(int i=1;i<=cnt;++i){
		f[1][i][cnt_1[i]]=1;
	}
	for(int fi=2;fi<=n;++fi){
		for(int i=1;i<=cnt;++i){
			for(int j=1;j<=cnt;++j){
				if((sta[i]&sta[j])||((sta[i]<<1)&sta[j])||((sta[i]>>1)&sta[j])) continue;
				for(int k=cnt_1[i];k<=m;++k){
					f[fi][i][k]+=f[fi-1][j][k-cnt_1[i]];
				}
			}
		
		}	
	}
	for(int i=1;i<=cnt;++i) ans+=f[n][i][m];
	cout<<ans<<"\n";
}

int main(){
	n=read(),m=read();
	pre();
	dp();
	
	
	
	return 0;
}
上一篇:【无标题】


下一篇:AcWing 1904. 奶牛慢跑(单调栈)