CF-1021-D. Baggage Claim

思路讲解

无向图边的重定向问题。

只告诉你奇数的块的位置，不告诉你偶数的块的位置，问有多少条路径（取模mod）

其实比较难的就是想样例4，多个块共用一个块，这个时候怎么办？

把他转化为图论问题，其实就是问这张图上有多少条 $1→5$ 路径？

这个有几种路径怎么算那？这其实根本用不到什么最小割，最大流什么的，割是用来解决不相交路径数量问题的。直接上dfs就行。

唉，这个直接暴力会TLE，毕竟数量太多了，一个一个统计一定会TLE的。

https://www.luogu.com.cn/problem/solution/CF2097B

其实想到见图了可以更进一步，直接将约束和点抽象为图。

主要就是把这个问题转化为了无向图方向确定问题。

AC代码

https://codeforces.com/contest/2097/submission/318339701

源代码

// Problem: B. Baggage Claim
// Contest: Codeforces - Codeforces Round 1021 (Div. 1)
// URL: https://codeforces.com/contest/2097/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,K,T;
ll fa[MAXN*2];
ll Ind[1010][1010];
ll rNode[MAXN*2],rEdge[MAXN*2];
bool vis[MAXN*2];
ll selfLoop[MAXN*2];

ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};


ll find(ll x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

inline void merge(ll x,ll y){
	ll fax=find(x),fay=find(y);
	if(x==y) {
		// 增加了一个自环，也算是加了
		rEdge[fax]+=1;
		selfLoop[fax]=true;
#ifdef LOCAL
    cerr << "--------selfLoop-----" << '\n';
#endif
		return;
	}else if(fax==fay){
		rEdge[fay]+=1;
		return;
	}
	rNode[fay]+=rNode[fax];
	rEdge[fay]+=rEdge[fax]+1;
	selfLoop[fay]|=selfLoop[fax];
	fa[fax]=fay;
}

inline void solve(){
	cin>>N>>M>>K;
	// init
	FOR(i,0,K*4){
		fa[i]=i;
		rNode[i]=1;
		rEdge[i]=0;
		vis[i]=false;
		selfLoop[i]=false;
	}
	FOR(i,0,N+5){
		FOR(j,0,M+5){
			Ind[i][j]=-INF;
		}
	}
	vector<arr> xy;
	FOR(i,1,K+1){
		ll x,y;
		cin>>x>>y;
		xy.pb({x,y});
		Ind[x][y]=INF;
	}
	
	ll tot=0;
	// 只有两个奇数块之间的曼哈顿距离严格为2，才会有偶数块使他们联通
	FOR(i,0,SZ(xy)-2){
		ll dis=abs(xy[i][0]-xy[i+1][0])+abs(xy[i][1]-xy[i+1][1]);
		if(dis!=2){
			cout<<0<<"\n";
			return;
		}
		vector<ll> inds;
		FOR(j,0,3){
			ll fx=xy[i][0]+dx[j],fy=xy[i][1]+dy[j];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(Ind[fx][fy]==INF) continue;
			// 确认是紧挨着的
			if(abs(fx-xy[i+1][0])+abs(fy-xy[i+1][1])!=1) continue;
			if(Ind[fx][fy]==-INF) Ind[fx][fy]=++tot;
			ll ind=Ind[fx][fy];
			inds.pb(ind);
		}
		FOR(i,0,SZ(inds)-2){
			ll ind1=inds[i],ind2=inds[i+1];
#ifdef LOCAL
    cerr << "ind1:"<<ind1<<" ind2:"<<ind2 << '\n';
#endif
			merge(ind1,ind2);
		}
		if(SZ(inds)==1){
#ifdef LOCAL
    cerr << "selfLoop:"<<inds.back() << '\n';
#endif
			merge(inds.back(),inds.back());
		}
	}
	ll ans=1;
	FOR(i,1,tot){
		ll fai=find(i);
		if(vis[fai]) continue;
		vis[fai]=true;
		ll rem=rNode[fai]-rEdge[fai];
#ifdef LOCAL
    cerr <<"fai:"<< fai<<" rem:"<<rem << '\n';
#endif
		if(rem==1){	// 树，有一个点入度为0，枚举这个点，就有N种选择
			ans*=rNode[fai];
			ans%=mod;
		}else if(rem==0){
			if(selfLoop[fai]){
				ans*=1;
			}else{
				ans*=2;
				ans%=mod;
			}
		}else{
			cout<<0<<"\n";
			return;
		}
	}
	ans%=mod;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2097/submission/318339701
*/

心路历程（WA，TLE，MLE……）

TLE

毕竟我的算法是去试每一条路径

https://codeforces.com/contest/2098/submission/317475573

源代码

// Problem: D. Baggage Claim
// Contest: Codeforces - Codeforces Round 1021 (Div. 2)
// URL: https://codeforces.com/contest/2098/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(5e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,K,T,A[MAXN];

vector<ll> g[MAXN*4];
ll Ind[1010][1010];
bool vis[MAXN*4];

ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};

ll ans=0;

void dfs(ll x,ll las){
	if(vis[x]) return;
	if(las+1!=x && x<=K) return;
	if(x==K){
		++ans;
		ans%=mod;
		return;
	}
	vis[x]=true;
	FOR(i,0,SZ(g[x])-1){
		ll fx=g[x][i];
		if(vis[fx]) continue;
		// if(fx<=K){
			// if(x<=K){
				// if(x+1!=fx) continue;
			// }
		// }
		// 如果说进入的点是我人为加出来的，需要延续上一个不是人为加出的点
// #ifdef LOCAL
    // cerr<<"x:"<<x<<" fx:"<<fx<<" las:"<<las<<"\n";
//     
// #endif
		if(x>K) dfs(fx,las);
		else dfs(fx,x);
		vis[fx]=false;

	}
}

inline void solve(){
	cin>>N>>M>>K;
	vector<arr> xy;
	// 只告诉你奇数的块的位置，不告诉你偶数的块的位置，问有多少条路径（取模mod）
	// initialize
	FOR(i,0,K*4){
		g[i].clear();
		vis[i]=false;
	}
	FOR(i,0,N+5){
		FOR(j,0,M+5){
			Ind[i][j]=-INF;
		}
	}
	FOR(i,1,K+1){
		ll x,y;
		cin>>x>>y;
		xy.pb({x,y});
		Ind[x][y]=INF;
	}
	
	ll tot=K+1;
	// 只有两个奇数块之间的曼哈顿距离严格为2，才会有偶数块使他们联通
	FOR(i,0,SZ(xy)-2){
		ll dis=abs(xy[i][0]-xy[i+1][0])+abs(xy[i][1]-xy[i+1][1]);
		if(dis!=2){
			cout<<0<<"\n";
			return;
		}
		FOR(j,0,3){
			ll fx=xy[i][0]+dx[j],fy=xy[i][1]+dy[j];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(Ind[fx][fy]==INF) continue;
			// 确认是紧挨着的
			if(abs(fx-xy[i+1][0])+abs(fy-xy[i+1][1])!=1) continue;
			if(Ind[fx][fy]==-INF) Ind[fx][fy]=++tot;
			ll ind=Ind[fx][fy];
			g[i].pb(ind);
			g[ind].pb(i+1);
		}
	}
	
// #ifdef LOCAL
	// cerr<<"T:"<<T<<"\n";
    // FOR(i,0,K*4){
    	// // if(g[i].empty()) break;
    	// cerr<<i<<":";
    	// FOR(j,0,SZ(g[i])-1){
    		// cerr<<g[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
    // cerr<<"\n";
// #endif
	ans=0;
	dfs(0,-1);
	ans%=mod;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
TLE https://codeforces.com/contest/2098/submission/317475573

*/

调试中一个样例出的一些问题

样例

1
5 5 11
2 5
3 4
4 5
5 4
4 3
5 2
4 1
3 2
2 1
1 2
2 3
1 4

通过暴力程序dfs我们得知，这个点直到（2，3）点，仍然有11条路径
但到了（1，4）点，我们就只有2条路径了。
因为有一个始源路径就是（2，5）->（3，3）->（3，4）,（2，3）->（1，4）也需要
所以说问题出在passNum的统计上，（3，3）作为始祖路径之一，早已不是只有一条路径通过了

问题代码

// Problem: D. Baggage Claim
// Contest: Codeforces - Codeforces Round 1021 (Div. 2)
// URL: https://codeforces.com/contest/2098/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(5e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,K,T,A[MAXN];

vector<ll> g[MAXN*4];
ll Ind[1010][1010];
// bool vis[MAXN*4];
ll passNum[MAXN*4];

ll dx[4]={1,0,-1,0};
ll dy[4]={0,-1,0,1};

inline void solve(){
	cin>>N>>M>>K;
	vector<arr> xy;
	// 只告诉你奇数的块的位置，不告诉你偶数的块的位置，问有多少条路径（取模mod）
	// initialize
	FOR(i,0,K*4){
		g[i].clear();
		// vis[i]=false;
		passNum[i]=0;
	}
	FOR(i,0,N+5){
		FOR(j,0,M+5){
			Ind[i][j]=-INF;
		}
	}
	FOR(i,1,K+1){
		ll x,y;
		cin>>x>>y;
		xy.pb({x,y});
		Ind[x][y]=INF;
	}
	
	ll tot=K+1;
	// 只有两个奇数块之间的曼哈顿距离严格为2，才会有偶数块使他们联通
	FOR(i,0,SZ(xy)-2){	// 节点加入算法
		ll dis=abs(xy[i][0]-xy[i+1][0])+abs(xy[i][1]-xy[i+1][1]);
		if(dis!=2){
			cout<<0<<"\n";
			return;
		}
		FOR(j,0,3){
			ll fx=xy[i][0]+dx[j],fy=xy[i][1]+dy[j];
			if(fx<1 || fx>N) continue;
			if(fy<1 || fy>M) continue;
			if(Ind[fx][fy]==INF) continue;
			// 确认是紧挨着的
			if(abs(fx-xy[i+1][0])+abs(fy-xy[i+1][1])!=1) continue;
			if(Ind[fx][fy]==-INF) Ind[fx][fy]=++tot;
			ll ind=Ind[fx][fy];
			g[i].pb(ind);
			g[ind].pb(i+1);
		}
	}
	
	ll ans=1;
	FOR(i,0,K-1){
		ll needLos=0;
		FOR(j,0,SZ(g[i])-1){
			ll node=g[i][j];	// 超出K的节点，通过上面的节点加入算法，可以保证该点一定有用
			// assert(node>=K);
			needLos+=passNum[node];
			passNum[node]+=(ans-passNum[node]);
		}
		ans=SZ(g[i])*ans-needLos;
#ifdef LOCAL
	
    cerr <<"i:"<<i<< " ans:"<<ans<<" SZ:"<<SZ(g[i])<<" needLos:"<<needLos << '\n';
#endif
	}
	
// #ifdef LOCAL
	// cerr<<"T:"<<T<<"\n";
    // FOR(i,0,K*4){
    	// // if(g[i].empty()) break;
    	// cerr<<i<<":";
    	// FOR(j,0,SZ(g[i])-1){
    		// cerr<<g[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
    // cerr<<"\n";
// #endif

	ans%=mod;
	if(ans<0) ans+=mod;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
TLE https://codeforces.com/contest/2098/submission/317475573
1
5 5 11
2 5
3 4
4 5
5 4
4 3
5 2
4 1
3 2
2 1
1 2
2 3
1 4
通过暴力程序dfs我们得知，这个点直到（2，3）点，仍然有11条路径
但到了（1，4）点，我们就只有2条路径了。
因为有一个始源路径就是（2，5）->（3，3）->（3，4）,（2，3）->（1，4）也需要
所以说问题出在passNum的统计上，（3，3）作为始祖路径之一，早已不是只有一条路径通过了

*/

inline void merge(ll x,ll y){
	ll fax=find(x),fay=find(y);
	if(x==y) {
		// 增加了一个自环，也算是加了
		rEdge[fax]+=1;
		selfLoop[fax]=true;
#ifdef LOCAL
    cerr << "--------selfLoop-----" << '\n';
#endif
		return;
	}else if(fax==fay){  // 这段斜体加粗要加上用来特判即不是自环，但在同一联通块的情况
		rEdge[fay]+=1;
		return;
	}
	rNode[fay]+=rNode[fax];
	rEdge[fay]+=rEdge[fax]+1;
	selfLoop[fay]|=selfLoop[fax];
	fa[fax]=fay;
}