2022/2/6

[P3381 【模板】最小费用最大流]( P3381 [模板]最小费用最大流 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) )

学习整理一下，(SPFA求费用流的模板)

const int qs=1e5;
const ll mod=998244353;
const ll inf=0x3f3f3f3f;
int n,m,s,t; 
int p,head[qs],nxt[qs],to[qs],val[qs],dis[qs];
void add(int fx,int tx,int dx,int cx){
	to[p]=tx;
	dis[p]=dx;
	nxt[p]=head[fx];
	val[p]=cx;
	head[fx]=p++;
}

void ist(int u,int v,int w,int c){
	add(u,v,w,c);
	add(v,u,0,-c);
}
int inq[qs],d[qs],pre[qs];

bool spfa(){
	for(int i=0;i<=n;++i){
		inq[i]=0;d[i]=inf,pre[i]=-1;
	}
	d[s]=0;inq[s]=1;
	queue<int> q; q.push(s);
	while(q.si){
		int u=q.front(); q.pop();
		inq[u]=0;
		for(int i=head[u];i!=-1;i=nxt[i]){
			if(dis[i]){//spfa是以费用val求最短路的，但流量不能忽略 
				int v=to[i];
				if(d[u]+val[i]<d[v]){
					d[v]=d[u]+val[i];
					pre[v]=i;
					if(!inq[v]){
						q.push(v);
						inq[v]=1;
					}
				}
			}
		}
	}
	return pre[t]!=-1;
}

void costflow(){//计算最小费用最大流 
	ll ret=0,ans=0;
	while(spfa()){
		int flow=inf;
		for(int i=t;i!=s;i=to[pre[i]^1]){
			//计算当前增广路的最小流量 
			flow=min(dis[pre[i]],flow);
		}
		ans+=flow;
		for(int i=t;i!=s;i=to[pre[i]^1]){
			dis[pre[i]]-=flow;
			dis[pre[i]^1]+=flow;
			ret+=val[pre[i]]*flow;
		}
	}
	cout<<ans<<" "<<ret<<"\n";
}

int main(){
	n=read(),m=read(),s=read(),t=read();
	memset(head,-1,sizeof(head));
	while(m--){
		int u,v,w,c;
		u=read(),v=read(),w=read(),c=read();
		ist(u,v,w,c);
	}
	costflow();
	return 0;
}

[ 多彩的树 ]( 多彩的树 (nowcoder.com) )

状压+dfs

k<=10,枚举所有可能出现的颜色状态 i。

在图中搜索 状态i 出现的所有连通块的大小，其中一块连通块大小为n，产生的贡献是\(n*(n+1)/2\)。

考虑到颜色多的情况会多算颜色少的情况，比如 1011 多算的情况有 ： 1010 1001 1000 0011 0010 0001 这6种，计算的时候要减去。

//找到比状态i小的且与状态i 1 的位置对应的下一个状态（学到了
for(int j=i&(i-1);j;j=(j-1)&i)

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define si size()
#define fi first
#define se second
#define pb push_back
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=1e5;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
ll n,k,a[qs],f[qs],u[qs],pw[107];
vector<int> v[qs];

ll dfs(int x,int sta){
	if(u[x]) return 0; u[x]=1;
	if((a[x]&sta) == 0) return 0;
	ll ret=1;
	for(int i=0;i<v[x].si;++i){
		int p=v[x][i];
		ret+=dfs(p,sta);
	}
	return ret;
}

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

int main(){
	
	n=read(),k=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		a[i]=(1<<(a[i]-1));
	}
	int x,y;
	for(int i=1;i<n;++i){
		x=read(),y=read();
		v[x].pb(y);
		v[y].pb(x);
	}
	ll ans=0;
	for(int i=1;i<(1<<k);++i){
		for(int j=1;j<=n;++j) u[j]=0;
		ll ret=0;
		for(int j=1;j<=n;++j){
			if(u[j]) continue;
			ll r=dfs(j,i);
			ret=(ret+r*(r+1)/2)%mod;
		}	
		f[i]=ret;
	}
	
	for(int i=1;i<(1<<k);++i){	
		for(int j=i&(i-1);j;j=(j-1)&i){
			f[i]=(f[i]-f[j]+mod)%mod;
		}
	}
	pw[1]=131;
	for(int i=2;i<=k;++i) pw[i]=pw[i-1]*131%mod;
	for(int i=1;i<(1<<k);++i){
		int cnt=get(i);
		ans=(ans+f[i]*pw[cnt]%mod)%mod;
	}
	ans=(ans+mod)%mod;
	cout<<ans<<"\n";
	return 0;
}

[ D. Range and Partition ]( Problem - D - Codeforces (Unofficial mirror site, accelerated for Chinese users) )

二分+暴力枚举

二分区间长度，判断一块区间[x,y]是否合法，需要在这段区间数的数量 num 减去 不在这段区间的数量 n-num 要 >=k

即 \(num-(n-num)>=k\)。

参考代码

#include<bits/stdc++.h>
#define ll  long long
#define pii pair<long long , long long >
#define si size()
#define fi first
#define se second
#define pb push_back
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=2e5+7;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;

int n,k,T,a[qs],b[qs]; 
vector< pii > ans;

int ck(int x){
	for(int i=1;i+x-1<=n;++i){
		if((b[i+x-1]-b[i-1])*2-n>=k) return i;
	}
	return 0;
}

int main(){
	T=read();
	while(T--){
		n=read(),k=read();
		ans.clear();
		for(int i=1;i<=n;++i) b[i]=0;
		for(int i=1;i<=n;++i) a[i]=read(),b[a[i]]++;
		for(int i=1;i<=n;++i) b[i]+=b[i-1];
		int l=1,r=n,ret=0,len=0;
		while(l<=r){
			int md=(l+r)/2;
			int sta=ck(md);
		//	cout<<"l="<<l<<" r="<<r<<" sta="<<sta<<"\n";
			if(sta) ret=sta,len=md,r=md-1;
			else l=md+1;
		}
		l=ret, r=ret+len-1; ret=0;
		int last=0,cnt=0;
		for(int i=1;i<=n;++i){
			if(cnt==k-1) break;
			if(a[i]<=r&&a[i]>=l) {
				ret++;
				if(ret>0){
					ans.pb({last+1,i});
					ret=0;
					last=i;
					cnt++;
				}	
			}
			else ret--;
		}
		ans.pb({last+1,n});
		cout<<l<<" "<<r<<"\n";
		for(int i=0;i<ans.si;++i){
			cout<<ans[i].fi<<" "<<ans[i].se<<"\n";
		}
	}
	
	
	return 0;
}