洛谷-Directed Roads-(基环树总结)

基环树性质：
1.n点n边。
2.一般都是每个点必然有个出边，因为这样才能保证每个连通块都是一个环。
3.如果是一个连通块话的话，必然有一个环
4.对于找环的大小，如果无向图并且不能忽略重边，那么建立单向边并且用第一种类型dfs求环大小。如果有向图，那么强连通缩点求大小。
5.对于求环的某条边，一般求某一条边就够了，用并查集求。

CF711D

题意：
就是给你一个n点n边的图，然后你可以让每条边定一个方向，使得这个图没有环。问你方案数同时取模。

思考：

1. n点n边明显基环树，如果这个图是联通的那么肯定就一个环，如果不联通可能就是多个联通块，不过每个联通块只有一个环的时候才是基环树森林。这个题保证了每个点必然会有边，所以一个联通块最多有一个环。
2. 既然定义方向后没有环，那么对于一个环而言，只有一种顺时针的和一种逆时针的不行，然后剩下的形式都可以。所以求出来每个环的方案数，然后对于那些不是环的边就是随意了。那么方案树就明显了。
3. 但是要注意的是，这里是给你无向的边，但是重边是有意义的，所以这里dfs求环的时候是一种方式。但是之前做的那题：2019秦皇岛-Forest Program，这题也是给你无向边让你求出来环，但是重边没有意义，dfs求环的时候是另一种方式。以上都是讨论无向图的，那么对于有向图怎么求环？用第一种dfs类型可以，也可以强连通缩点求，只要这个环的大小>=2那么就是可以的。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];
int siz[N],vis[N];

vector<int > v;
vector<int > e[N];

void dfs(int now,int p)
{
	vis[now] = 1;
	siz[now] = siz[p]+1;
	for(auto spot:e[now])
	{
		if(!vis[spot]) dfs(spot,now);
		else if(vis[spot]==1) v.pb(siz[now]-siz[spot]+1);
	}
	vis[now] = 2;
}

int ksm(int a,int b)
{
	int sum = 1;
	while(b)
	{
		if(b&1) sum = sum*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return sum;
}

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++)
	{ 
		cin>>va[i];
		e[va[i]].pb(i);
	}
	int ans = 1;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]) dfs(i,0);
	}
	int sum = 0;
	for(auto t:v)
	{
		sum += t;
		ans = ans*(ksm(2,t)-2)%mod; //只有两种方式不行
	}
	ans = ans*ksm(2,n-sum)%mod; //剩下的随便
	ans = (ans%mod+mod)%mod;
	cout<<ans;
	return 0;
}
无向图不忽略重边
e[a].pb(b)建立单向边
void dfs(int now,int p)
{
	vis[now] = 1;
	siz[now] = siz[p]+1;
	for(auto spot:e[now])
	{
		if(!vis[spot]) dfs(spot,now);
		else if(vis[spot]==1) v.pb(siz[now]-siz[spot]+1);
	}
	vis[now] = 2;
}
无向图忽略重边
e[a].pb(b);
e[b].pb(a);建立双向边
void dfs(int now,int p)
{
	col[now] = 1;
	siz[now] = siz[p]+1;
	for(auto spot:e[now])
	{
		if(spot==p) continue;
		if(!col[spot]) dfs(spot,now);
		else if(col[spot]==1) v.pb(siz[now]-siz[spot]+1);
	}
	col[now] = 2;
}
有向图忽略重边：
e[a].pb(b)建立单向边
强连通缩点后，找出所有环的大小>=2的即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

洛谷-P1453 城市环路

题意：
就是给你n个点n条边，保证这个图联通，然后每个点有个人流量，小A想在某些点开店，但是一条边的两个端点不能同时开店。第i个点开店的带来的价值是va[i]*k，k是一个实数。现在问你小A最大可以获得的价值。

思考：

1. 假如是n点n-1条边，也就是一个树的话，那么就是经典的没有上司舞会那题。但是这个多了一条边，也就是多了那个环。这不能树上跑dp了。但是实际上就这一个环，我完全可以把这个环的某个点断开分两种情况讨论。
2. 比如断开的边的两个点分别是A,B，那么我完全可以从A开始跑dp，但是我要保证B不选，这样最后的答案就是max(A选B不选，A不选B不选)，保证了树的dp，还保证了A和B这条边没违规。怎么保证不选B呢？完全可以让va[B] = -inf就可以了。同理从B开始跑dp，va[A] = -inf一样。
3. 然后有个疑惑点就是，一个环有好几个边，为什么我就讨论去掉其中某一条边就可以了？因为你去掉其中一条边，讨论了两种情况，保证了这条边的合法性。对于剩下的边就是一个dp，这个dp包含了所有情况。所以你求出来就是所有的情况了。就算你这个环的所有边都讨论一次答案也是一样的。和之前做过的UPC那题一样：UPC-Cards,断环成链即可，只要讨论第一个点要不要和最后一个点相连的情况然后dp就可以了。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];
int acc[N];
int dp[N][2];
int A,B;

vector<int > e[N];

int find(int x)
{
	if(x!=acc[x]) acc[x] = find(acc[x]);
	return acc[x];
}

void dfs(int now,int p)
{
	dp[now][1] = va[now];
	for(auto spot:e[now])
	{
		if(spot==p) continue;
		dfs(spot,now);
		dp[now][1] += dp[spot][0];
		dp[now][0] += max(dp[spot][1],dp[spot][0]);
	}
}

int solve1()
{
	int tp = va[B];
	va[B] = -inf;
	for(int i=1;i<=n;i++) dp[i][0] = dp[i][1] = 0;
	dfs(A,0);
	va[B] = tp;
	return max(dp[A][0],dp[A][1]);
}

int solve2()
{
	int tp = va[A];
	va[A] = -inf;
	for(int i=1;i<=n;i++) dp[i][0] = dp[i][1] = 0;
	dfs(B,0);
	va[A] = tp;
	return max(dp[B][0],dp[B][1]);
}

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) acc[i] = i;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;a++,b++;
		int t1 = find(a),t2 = find(b);
		if(t1==t2) //要去掉成环的那个条边
		{
			A = a,B = b;
			continue;
		}
		acc[t1] = t2;
		e[a].pb(b);
		e[b].pb(a);
	}
	int maxn = 0;
	maxn = max(maxn,solve1());
	maxn = max(maxn,solve2());
	db tp;cin>>tp;
	db ans = maxn*tp;
	printf("%.1lf",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

P2607 骑士

题意：
就是给你n个骑士，每个骑士有个自己的能力值和他讨厌的人。现在让你选择一些骑士，这些骑士之间不能有自己讨厌的人。问你选出所有骑士的最大战斗力。

思考：

1. 这题和上题一样，一条边的两个点不能同时选，经典的没有上司的舞会。但是这个图不一定是联通的，但是保证了每个点必然有一条边，所以每个连通块必然是一个环。然后对每个环段环跑dp就可以了。

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e6+10,M = 2010;

int T,n,m,k;
int va[N];
int acc[N];
int dp[N][2];
int vis[N],st[N],A,B;

vector<int > e[N];

int find(int x)
{
	if(x!=acc[x]) acc[x] = find(acc[x]);
	return acc[x];
}

void get(int now,int p)
{
	vis[now] = 1;
	if(st[now])
	{
		if(A==-1) A = now;
		else B = now;
	}
	for(auto spot:e[now])
	{
		if(!vis[spot]) get(spot,now);
	}
}

void dfs(int now,int p)
{
	dp[now][0] = 0,dp[now][1] = va[now];
	for(auto spot:e[now])
	{
		if(spot==p) continue;
		dfs(spot,now);
		dp[now][1] += dp[spot][0];
		dp[now][0] += max(dp[spot][0],dp[spot][1]);
	}
}

int solve1()
{
	int tp = va[B];
	va[B] = -inf;
	dfs(A,0);
	va[B] = tp;
	return max(dp[A][0],dp[A][1]);
}

int solve2()
{
	int tp = va[A];
	va[A] = -inf;
	dfs(B,0);
	va[A] = tp;
	return max(dp[B][0],dp[B][1]);
} 

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) acc[i] = i;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		va[i] = a;
		int t1 = find(i),t2 = find(b);
		if(t1==t2)
		{
			st[i] = st[b] = 1; 
			continue;
		}
		acc[t1] = t2;
		e[i].pb(b);
		e[b].pb(i);
	}
	int ans = 0;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			A = -1,B = -1;
			get(i,0);
			ans += max(solve1(),solve2());
		}
	}
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

ABC-F - Well-defined Path Queries on a Namori

题意：
就是给你一个n个点n条边的连通图，然后给你m次询问，问你a和b两个点之间的简单路径是否唯一。

思考：

1. 很明显就是基环树，我可以直接把这个环给断掉，拿出其中两个端点A,B，让其中一个当根节点跑一边dfs，那么这个环的所有点就是从B点往上爬直到根节点A。
2. 这个所有环上的点也就成了一条链，然后每次给a和b，问是否有不同的路径。刚开始我总想根据a和b的lca来判断，但是画画图发现，并不是这样而且还情况多复杂。实际上就对于每个环上的点，看看他的所有孩子节点都是什么，给他标志上自己的颜色。那么对于两个点是否有多个路径，那么就看看a和b是否在一个子树上，如果不在，那么就有第二条路径。
3. 当然只要能画图模拟出找到这个环，对环上的点的子树去染色。这个环还有种方法，可以拓扑序一直把度为1的删掉，最后剩下的就是环上的点，不过这要保证只有一个环，要不然你不知道剩下的点是在那个环里面。
4. 一个重要的利器还是画图，只要图多画画，一会就把清理考虑清楚了。

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];
int acc[N][25],dep[N],cnt=22;
int fa[N],vis[N],col[N],A,B;

vector<int > e[N];

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

void dfs(int now,int p)
{
	acc[now][0] = p;
	dep[now] = dep[p]+1;
	for(auto spot:e[now])
	{
		if(spot==p) continue;
		dfs(spot,now);
	}
}

void get(int now,int p,int best)
{
	col[now] = best;
	for(auto spot:e[now])
	{
		if(spot==p||vis[spot]) continue; //不能走是环上的点
		get(spot,now,best);
	}
}

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) fa[i] = i;
	for(int i=1;i<=n;i++)
	{
		int a,b;
		cin>>a>>b;
		int t1 = find(a),t2 = find(b);
		if(t1==t2)
		{
			A = a,B = b;
			continue;
		}
		fa[t1] = t2;
		e[a].pb(b);
		e[b].pb(a);
	}
	dfs(A,0);
	int now = B;
	while(now)
	{
		vis[now] = 1;
		now = acc[now][0];
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) get(i,0,i); //给环上每个点的子树分配颜色
	}
	cin>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		if(col[a]!=col[b]) cout<<"No\n";
		else cout<<"Yes\n";
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88