ABC 214 G,H 题解

本文主要是介绍ABC 214 G,H 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

ABC 214 G,H 题解

G

考虑建一张图。

途中\(p_i,q_i\)之间有一条边。

则问题转化成，在每条边上写上两两不同的数字，使得每一条边写的数字和两端的数字不同。

考虑容斥。

钦定一些边，然后给边定向，使得每一个点的出度\(\leq 1\)。

可以发现构成的连通块是个环，直接破环为链dp。

然后对于所有环做一次卷积就是答案。

时间复杂度\(O(N^2\log N)\)。

code:

#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MOD=1e9+7;
const int MAXN=3003;
int fact[MAXN];
int n,fa[MAXN],siz[MAXN];
int root(int x){
	return fa[x]=(fa[x]==x? x:root(fa[x]));
}
void merge(int u,int v){
	if(root(u)==root(v)) return ;
	siz[root(v)]+=siz[root(u)];
	fa[root(u)]=root(v);
}
int dp[2][2][MAXN][MAXN];
void add(int & A,int B){
	A+=B;
	if(A>=MOD) A-=MOD;
}
vector<int> calc(int len){
	if(len==1) return {1,1};
	rep(f,2) rb(i,1,len) memset(dp[0][f][i],0,sizeof(dp[0][f][i])),memset(dp[1][f][i],0,sizeof(dp[1][f][i]));
	dp[0][1][2][1]=1;
	dp[1][0][2][1]=1;
	dp[0][0][2][0]=1;
	vector<int> Ret(len+1,0);
	rb(i,2,len){
		rep(j,2)
			rep(f,2){
				rep(k,i)
					if(dp[j][f][i][k]){
						int val=dp[j][f][i][k];
						if(i==len){
							add(Ret[k],val);
							if(!j) add(Ret[k+1],val);
							if(!f) add(Ret[k+1],val);
						}
						else{
							add(dp[j][0][i+1][k],val);
							if(!f) add(dp[j][0][i+1][k+1],val);
							add(dp[j][1][i+1][k+1],val);
						}
					}
			}
	}
	return Ret;
}
vector<int> mul(vector<int> A,vector<int> B){
	vector<int> ret(A.size()+B.size()-1,0);
	rep(i,A.size()) rep(j,B.size()) add(ret[i+j],1ll*A[i]*B[j]%MOD);
	return ret;
}
int q[MAXN],p[MAXN];
int main(){
	fact[0]=1;
	rb(i,1,3000) fact[i]=1ll*fact[i-1]*i%MOD;
	scanf("%d",&n);
	rb(i,1,n) scanf("%d",&p[i]);
	rb(i,1,n) scanf("%d",&q[i]);
	rb(i,1,n) fa[i]=i,siz[i]=1;
	rb(i,1,n) merge(q[i],p[i]);
	vector<vector<int> > poly;
	rb(i,1,n) if(root(i)==i) poly.PB(calc(siz[i]));
	priority_queue<mp,vector<mp>,greater<mp> > heap;
	rep(i,poly.size()) heap.push(II(poly[i].size(),i));
	while(heap.size()>=2){
		int i,j;
		i=heap.top().SEC;
		heap.pop();
		j=heap.top().SEC;
		heap.pop();
		poly[i]=mul(poly[j],poly[i]);
		heap.push(II(poly[i].size(),i));
	}
	int i=heap.top().SEC;
	int ans=0;
	rep(j,poly[i].size()){
		if(j&1)
		add(ans,MOD-1ll*fact[n-j]%MOD*poly[i][j]%MOD);
		else
		add(ans,1ll*fact[n-j]%MOD*poly[i][j]%MOD);
	}
	cout<<ans<<endl;
	return 0;
}

H

很显然是费用流。

但是spfa会被卡。

需要用dijkstra费用流。

方法：令\(h[i]\)表示当前从\(s\)到\(i\)的最短路减去上一次增广前\(s\)到\(i\)的最短路。

然后考虑对\(h\)跑对短路。

边权\(u\rightarrow v,w\)变成\(w+dis[u]-dis[v]\)。可以发现这个总是\(\geq 0\)。

然后就做完了。

code:

#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
#define int LL
typedef pair<LL,LL> mp;
/*}
*/
const int GRAPH_SIZE= 4e5+10;
int s=0,t=GRAPH_SIZE-1;
struct EDGE{
	int u,v,c,cos;
};
vector<EDGE> e;
vector<int> each[GRAPH_SIZE];
int maxflow,mincost;
int flow[GRAPH_SIZE];
int dis[GRAPH_SIZE],las[GRAPH_SIZE],h[GRAPH_SIZE];
bool fi=0;
int cnt=0;
bool spfa(){
	flow[s]=1e17;
	if(!fi){
		fi=1;
		fill(dis,dis+GRAPH_SIZE,1e17);
		dis[s]=0;
		rb(now,0,cnt*2){
			if(dis[now]==1e17) continue;
//			cerr<<now<<' '<<dis[now]<<endl;
			for(auto it:each[now]){
				int to,f,c;
				to=e[it].v;
				f=e[it].c;
				c=e[it].cos;
				if(f<=0) continue;
				assert(to>now);
				if(dis[to]>dis[now]+c){
					dis[to]=dis[now]+c;
					las[to]=it;
					flow[to]=min(flow[now],f);
				}
			}
		}
	}
	else{
		fill(h,h+GRAPH_SIZE,1e17);
		h[s]=0;
		priority_queue<mp,vector<mp>,greater<mp> > heap;
		heap.push(II(0,s));
		while(!heap.empty()){
			mp Now=heap.top();
			heap.pop();
			if(Now.FIR!=h[Now.SEC]) continue;
			int now=Now.SEC;
			for(auto it:each[now]){
				int to,f,c;
				to=e[it].v;
				f=e[it].c;
				c=e[it].cos+dis[now]-dis[to];
				if(f<=0) continue;
				if(h[to]>h[now]+c){
					h[to]=h[now]+c;
					las[to]=it;
					flow[to]=min(flow[now],f);
					heap.push(II(h[to],to));
				}
			}
		}
		rep(i,GRAPH_SIZE) dis[i]=min((LL)(1e17),dis[i]+h[i]);
	}
//	cerr<<dis[t]<<endl;
	return dis[t]<=1e16;
}
void KM(){
	while(spfa()){
		maxflow+=flow[t];
		mincost+=dis[t]*flow[t];
//		cout<<mincost<<" "<<maxflow<<endl;
		int now=t;
		while(now!=s){
			e[las[now]].c-=flow[t];
			e[las[now]^1].c+=flow[t];
			now=e[las[now]].u;
		}
	}
}
void make_edge(int U,int V,int C,int COS){
	EDGE tmp;
	tmp.u=U;
	tmp.v=V;
	tmp.c=C;
	tmp.cos=COS;
	e.PB(tmp);
	each[U].PB(e.size()-1);
	swap(tmp.u,tmp.v);
	tmp.c=0;
	tmp.cos=-COS;
	e.PB(tmp);
	each[V].PB(e.size()-1);
}
const int MAXN=2e5+10;
int n,m,k;
int in[MAXN],out[MAXN];
int belong[MAXN];
vector<int> g[MAXN],rg[MAXN];
int u[MAXN],v[MAXN];
stack<int> sta;
bool vis[MAXN];
map<mp,bool> app;
int x[MAXN];
void dfs(int now){
	vis[now]=1;
	for(auto it:g[now]) if(!vis[it]) dfs(it);
	sta.push(now);
}
void rdfs(int now){
	belong[now]=cnt;
	for(auto it:rg[now]) if(!belong[it]) rdfs(it);
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	rb(i,1,m){
		scanf("%lld%lld",&u[i],&v[i]);
		g[u[i]].PB(v[i]);
		rg[v[i]].PB(u[i]);
	}
//	cout<<g[1].size()<<endl;
	rb(i,1,n)
	if(!vis[i]) dfs(i);
	while(!sta.empty()){
		int now=sta.top();
		sta.pop();
		if(!belong[now]){
			++cnt;
			rdfs(now);
		}
	}
//	cout<<"!"<<cnt<<endl;
	rb(i,1,n){
		LL xx;
		scanf("%lld",&xx),x[belong[i]]+=xx;
	}
	rb(i,1,cnt) in[i]=i*2-1,out[i]=i*2;
	make_edge(s,in[belong[1]],k,0);
	rb(i,1,m){
		int U,V;
		U=belong[u[i]];
		V=belong[v[i]];
		if(U==0||V==0) continue;
		if(U!=V&&!app[II(U,V)]){
			app[II(U,V)]=1;
			assert(U<V);
//			cout<<out[U]<<" "<<in[V]<<endl;
			assert(out[U]<in[V]);
			make_edge(out[U],in[V],k,0);
		}
	}
//	cout<<cnt<<endl;
	rb(i,1,cnt) make_edge(in[i],out[i],1,-x[i]),make_edge(in[i],out[i],k,0);
	rb(i,1,cnt) make_edge(out[i],t,k,0);
	KM();
	cout<<-mincost<<endl;
	return 0;
}

这篇关于ABC 214 G,H 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程

ABC 214 G,H 题解

ABC 214 G,H 题解

G

H

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯