Codeforces 1383F - Special Edges（状态压缩+最大流）

首先暴力显然是不行的，如果你暴力最大流过了我请你吃糖

注意到本题的 \(k\) 很小，考虑以此为突破口解题。根据最大流等于最小割定理，点 \(1\) 到点 \(n\) 的最大流，等于边权和最小的边集 \(E\) 的边权和，满足割掉 \(E\) 中的边后 \(1\) 与 \(n\) 不连通（这里稍微多说几句，关于最大流最小割的“割”，最原始的定义是将点集 \(V\) 分成两个点集 \(V_1,V_2\)，满足 \(V_1\cup V_2=V\)，并且 \(S\in V_1,T\in V_2\)，并且定义了割的权值 \(\sum\limits_{u\in V_1,v\in V_2}c(u,v)\)，最上面的“割掉 \(E\) 的边后 \(1\) 与 \(n\) 不连通”有本质区别，上述结论只是它的一个推论）。我们不妨枚举 \(E\) 与特殊边集合的并集 \(S\)，也就是说对于 \(S\) 中的特殊边我们强制要求它必须被割掉，对于不在 \(S\) 中的特殊边我们强制要求它不能被割掉。显然这样的 \(S\) 总共有 \(2^k\) 个，因此我们可以对每个 \(S\) 计算答案并更新 \(ans\)。

那么怎么计算集合 \(S\) 的答案呢？首先集合 \(S\) 中的边的权值是肯定要累加入答案中的，因此我们首先求出 \(\sum\limits_{e\in S}w_e\)，这个显然可以通过类似于前缀和的东西以单组询问 \(2^k\) 的复杂度预处理出来。接下来考虑怎么计算不在 \(S\) 中的边的贡献，我们建一张新图，包含所有非特殊边和所有不在 \(S\) 中的特殊边，其中非特殊边的容量就是其本身的容量，特殊边的容量为 \(\infty\)，因为它不能被割掉，当然由于 \(w\le 25\) 你也可以将其设为 \(25\)。至于 \(S\) 中的特殊边……既然它已经被鸽割掉了就不用管它了。我们只需在这张图上跑一遍最小割即最大流即可。

不过问题又来了，根据常识点数边数 \(10^4\) 级别的图跑最大流复杂度大约是 \(10^7\) 级别的，而我们对 \(2^k\) 个集合每个都跑一遍最大流，复杂度高达 \(10^{10}\)，无法通过。不过注意到这 \(2^k\) 张图都是在原本非特殊边构成的图的基础上，添加 \(\le k\) 条容量为 \(25\) 的特殊边构成的，因此我们考虑先对非特殊边跑一遍最大流求出它的残余网络，然后对所有集合 \(S\) 在残余网络上加边跑出新增的流量。注意到这题边的容量很小，因此 Dinic 复杂度甚至不如最朴素的 FF 算法。具体来说，我们随便找一条 \(1\to n\) 的增广路径并更新流量，可以证明这样做的复杂度是 \(\mathcal O(wm)\)，因此总复杂度就降到了 \(2^k·wm+q2^k\)。

这是蒟蒻第一次写 FF 哦，早安，Dinic 人

还有就是此题非常卡常，既卡 TLE 又卡 MLE，我大约交了十几发才通过，这里给出几个小卡常技巧：

由于此题边数 \(\le 2\times 10^4<2^{16}\)，因此数组可以开成 short，这样空间常数可小一半。
在 FF 的过程中，如果发现已经 BFS 到了 \(n\) 就 break 掉，及时停止，也算是一个小小的剪枝吧。
我是暴力开 \(2^{10}\) 个图的，我们记 \(G_S\) 为加入 \(S\) 中的边后跑完最大流后的残余网络，在计算 \(G_S\) 的最大流时，你不必以 \(G_0\) 为基础加入 \(|S|\) 条边，可以用 lowbit 找到 \(S\) 中最小的元素并以 \(G_{S-\{x\}}\) 为基础，这样只用加入一条边，常数会小不少。
记得写读入优化，这题读入量有点大。

然鹅还是跑得很慢啊……最慢的点跑了 4.5s，几乎是卡时限过题，不保证下次提交依然可以通过。

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)+1;

	}

	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}

	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}

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

}

using namespace fastio;

void chkmin(int &x,int y){(y-x>>31)&&(x=y);}

const int MAXN=1e4;

const int MAXM=2e4;

const int MAXK=10;

const int MAXMSK=1<<10;

const int INF=0x3f3f3f3f;

int n,m,k,qu,sum[MAXMSK+5];

int su[MAXK+5],sv[MAXK+5],sw[MAXK+5];

struct graph{

	short int hd[MAXN+5],to[MAXM+5],nxt[MAXM+5],cap[MAXM+5],ec=1;

	void adde(int u,int v,int w){

		to[++ec]=v;cap[ec]=w;nxt[ec]=hd[u];hd[u]=ec;

		to[++ec]=u;cap[ec]=0;nxt[ec]=hd[v];hd[v]=ec;

	} short int dep[MAXN+5],now[MAXN+5];

	bool getdep(){

		memset(dep,-1,sizeof(dep));dep[1]=0;

		queue<int> q;q.push(1);now[1]=hd[1];

		while(!q.empty()){

			int x=q.front();q.pop();

			for(int e=hd[x];e;e=nxt[e]){

				int y=to[e],z=cap[e];

				if(z&&!~dep[y]){

					dep[y]=dep[x]+1;

					now[y]=hd[y];q.push(y);

				}

			}

		} return ~dep[n];

	}

	int getflow(int x,int f){

		if(x==n) return f;int ret=0;

		for(short int &e=now[x];e;e=nxt[e]){

			int y=to[e],z=cap[e];

			if(dep[y]==dep[x]+1&&z){

				int w=getflow(y,min(f-ret,z));

				ret+=w;cap[e]-=w;cap[e^1]+=w;

				if(ret==f) return ret;

			}

		} return ret;

	}

	int dinic(){

		int ret=0;

		while(getdep()) ret+=getflow(1,INF);

		return ret;

	}

	int ff_bfs(){

		memset(dep,-1,sizeof(dep));dep[1]=0;

		queue<int> q;q.push(1);

		while(!q.empty()){

			int x=q.front();q.pop();

			for(int e=hd[x];e;e=nxt[e]){

				int y=to[e],z=cap[e];

				if(z&&!~dep[y]){

					dep[y]=dep[x]+1;now[y]=e;

					q.push(y);if(~dep[n]) break;

				}

			} if(~dep[n]) break;

		} if(!~dep[n]) return 0;

		int mn=25;

		for(int i=n;i^1;i=to[now[i]^1]) chkmin(mn,cap[now[i]]);

		for(int i=n;i^1;i=to[now[i]^1]) cap[now[i]]-=mn,cap[now[i]^1]+=mn;

		return mn;

	}

	int ff(){

		int delta=0,ret=0;

		while(delta=ff_bfs()) ret+=delta;

		return ret;

	}

} g[MAXMSK+5];

int flw[MAXMSK+5];

int main(){

	read(n);read(m);read(k);read(qu);

	for(int i=1;i<=k;i++) read(su[i]),read(sv[i]),read(sw[i]);

	for(int i=k+1,u,v,w;i<=m;i++) read(u),read(v),read(w),g[0].adde(u,v,w);

	flw[0]=g[0].dinic();

	for(int i=1;i<(1<<k);i++){

		int lwb=i&-i;g[i]=g[i^lwb];

		int id=32-__builtin_clz(lwb);

		g[i].adde(su[id],sv[id],25);

		flw[i]=flw[i^lwb]+g[i].ff();

//		printf("%d %d\n",i,flw[i]);

	}

//	if(n==9743&&qu==200000&&sv[1]==209) cout<<clock()<<endl;

	while(qu--){

		for(int i=1;i<=k;i++) read(sw[i]);

		for(int i=1;i<(1<<k);i++){

			int lwb=i&-i,id=32-__builtin_clz(lwb);

			sum[i]=sum[i^lwb]+sw[id];

		} int ans=INF;

		for(int i=0;i<(1<<k);i++){

//			printf("%d %d %d\n",i,sum[i],flw[((1<<k)-1)^i]);

			chkmin(ans,sum[i]+flw[((1<<k)-1)^i]);

		} print(ans);putc('\n');

	} print_final();

	return 0;

}

巴特西

Codeforces 1383F - Special Edges（状态压缩+最大流）

最新文章

热门文章