Codeforces 1373F - Network Coverage（模拟网络流）

提供一个模拟网络流的题解。

首先我们觉得这题一脸可以流的样子，稍微想想可以想到如下建图模型：

建立源点 \(S,T\) 和上下两排点，不妨设上排点为 \(x_1,x_2,\cdots,x_n\)，下排点为 \(y_1,y_2,\cdots,y_n\)。
对于每个 \(i\) 我们连一条 \(S\to x_i\)，容量为 \(b_i\) 的边，表示每个基站最多提供 \(b_i\) 个网络服务。
对于每个 \(i\)，我们连边 \(x_i\to y_i,x_i\to y_{i\bmod n+1}\)，权值均为 \(\infty\)，表示基站 \(i\) 可以为家庭 \(i\) 和家庭 \(i\bmod n+1\) 提供网络服务。
连边 \(y_i\to T\)，权值 \(a_i\)，表示家庭 \(i\) 需要 \(a_i\) 个网络服务。

然后跑最大流看看最大流是否等于 \(\sum\limits_{i=1}^na_i\) 即可。

由于此题 \(n\) 高达 \(10^6\)，因此直接跑最大流显然是不可取的。因此考虑模拟网络流，也就是用最小割解决最大流的思路。注意到图是一个环形结构，直接做可能会出现后效性有关的问题，因此我们不妨先解决链的情况，即，假设 \(x_n\to y_1\) 的边不存在。设 \(dp_{i,j}(j\in\{0,1\})\) 表示现在只考虑 \(x_1,x_2,\cdots,x_i,y_1,y_2,\cdots,y_i,S,T\) 的导出子图，\(S,T\) 在导出子图中不连通且 \(S\to x_i\) 的边的状态为 \(j\)（\(0\)：连上，\(1\)：断开）的最小代价，那么有 \(dp_{i,j}=\min\limits_{k\in\{0,1\}}dp_{i-1,k}+kb_i+[j=0\lor k=0]·a_i\)，边界条件 \(dp_{0,0}=0\)。

接下来考虑环的情况，其实感觉会了链的情况，环的情况就异常 trivial 了。按照套路枚举 \(S\to x_n\) 的边连上还是断开，设为 \(c\)，那么与链的情况不同之处在于，边界条件变为 \(dp_{0,c}=0\)，因为 \(S\to x_n\) 的边连上等价于 \(x_n\to y_1\) 的边没有被断开，最后用 \(dp_{n,c}\) 更新答案即可。

时间复杂度线性。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

#define mt make_tuple

#define eprintf(...) fprintf(stderr,__VA_ARGS__)

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

typedef unsigned int u32;

typedef unsigned long long u64;

typedef long double ld;

namespace fastio{

	#define FILE_SIZE 1<<23

	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;

	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}

	inline void putc(char x){(*p3++=x);}

	template<typename T> void read(T &x){

		x=0;char c=getchar();T neg=0;

		while(!isdigit(c)) neg|=(c=='-'),c=getchar();

		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

		if(neg) x=-x;

	}

	template<typename T> void recursive_print(T x){

		if(!x) return;

		recursive_print(x/10);putc(x%10+'0');

	}

	template<typename T> void print(T x){

		if(!x) putc('0');if(x<0) putc('-'),x=-x;

		recursive_print(x);

	}

	template<typename T> void print(T x,char c){print(x);putc(c);}

	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}

}

template<typename Tv,int limN,int limM> struct link_list{

	int hd[limN+5],nxt[limM+5],item_n=0;Tv val[limM+5];

	void clear(){memset(hd,0,sizeof(hd));item_n=0;}//be aware of the TC of memset

	void ins(int x,Tv y){val[++item_n]=y;nxt[item_n]=hd[x];hd[x]=item_n;}

};

using namespace fastio;

const int MAXN=1e6;

const ll INF=0x3f3f3f3f3f3f3f3fll;

int n,a[MAXN+5],b[MAXN+5];ll dp[MAXN+5][2];

void solve(){

	read(n);ll sum=0,res=INF;

	for(int i=1;i<=n;i++) read(a[i]),sum+=a[i];

	for(int i=1;i<=n;i++) read(b[i]);

	for(int _=0;_<2;_++){

		for(int i=0;i<=n;i++) dp[i][0]=dp[i][1]=INF;

		dp[0][_]=0;

		for(int i=1;i<=n;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++)

			chkmin(dp[i][j],dp[i-1][k]+j*b[i]+(!(j&k))*a[i]);

		chkmin(res,dp[n][_]);

	} //printf("%lld\n",res);

	printf("%s\n",(res==sum)?"YES":"NO");

}

int main(){int qu;read(qu);while(qu--) solve();return 0;}

巴特西

Codeforces 1373F - Network Coverage（模拟网络流）

最新文章

热门文章