CF-1021-D. Baggage Claim · znzryb
## 思路讲解
无向图边的重定向问题。
只告诉你奇数的块的位置，不告诉你偶数的块的位置，问有多少条路径（取模mod）
其实比较难的就是想样例4，多个块共用一个块，这个时候怎么办？
把他转化为图论问题，其实就是问这张图上有多少条 $1→5$ 路径？
这个有几种路径怎么算那？这其实根本用不到什么最小割，最大流什么的，割是用来解决不相交路径数量问题的。直接上dfs就行。
唉，这个直接暴力会TLE，毕竟数量太多了，一个一个统计一定会TLE的。
[https://www.luogu.com.cn/problem/solution/CF2097B](https://www.luogu.com.cn/problem/solution/CF2097B)
其实想到见图了可以更进一步，直接将约束和点抽象为图。
主要就是把这个问题转化为了无向图方向确定问题。
## AC代码
[https://codeforces.com/contest/2097/submission/318339701](https://codeforces.com/contest/2097/submission/318339701)
::: 源代码
```cpp
// 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](https://codeforces.com/contest/2098/submission/317475573)
::: 源代码
```cpp
// 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
*/
```
:::
调试中一个样例出的一些问题
::: 样例
```cpp
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）作为始祖路径之一，早已不是只有一条路径通过了
::: 问题代码
```cpp
// 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）作为始祖路径之一，早已不是只有一条路径通过了
*/
```
:::
```cpp
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;
}
```