缩点+图论路径网络流：1114T4

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134407471

http://cplusoj.com/d/senior/p/SS231114D

重新梳理一下题目

我们先建图 x→yx\to y ，然后对点分类：原串出现点，原串未出现点。

假如我们对一个原串出现点进行了操作，那么它剩余所有出边我们立刻去操作必然没有影响。所以我们只要所有原串出现点都操作一遍即可（如果有出边），那么我们就把边问题变成了点问题。

考虑一次置换过程抽象为原串上的一条链，那必然会造成一个损失。而要消除这个损失，一个方法是使链的尾端为原串未出现点。

对于图上路径问题，我们可以直接缩点，因为一个强连通里，我们必然可以从一个进一个出。最后变成了一个DAG。

这就变成了一个二分图问题。每个点可以向其连通的点连边，只要满足这个点还有出度，或者这个点为原串未出现点。

而左边为匹配的点就是代价了。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 150
//#define M
//#define mo
namespace Flow {
	#define int long long
	struct mf_graph {
		struct node {
			int x, y, z, n; 
		}; 
		vector<node>d; 
		vector<int>h, H, dep; 
		queue<int>q; 
		int k; 
		int u, v, w, S, T, ans=0; 
		void reset(int n) {
			h.resize(n+5); k=1; d.resize(2); 
			H.resize(n+5); dep.resize(n+5); 
		}
		void cun(int x, int y, int z) {
			++k; d.pb({x, y, z, h[x]}); 
			d[k].n=h[x]; h[x]=k;
		}
		void add_edge(int x, int y, int z) {
//			swap(x, y); 
//			debug("%lld -> %lld %lld\n", x, y, z); 
			cun(x, y, z); cun(y, x, 0); 
		}
		int bfs() {
			while(!q.empty()) q.pop(); 
			fill(dep.begin(), dep.end(), -1); 
			h=H; 
			dep[S]=1; q.push(S); 
			while(!q.empty()) {
				u=q.front(); q.pop(); 
				for(int g=h[u]; g; g=d[g].n) {
					v=d[g].y; w=d[g].z; 
					if(w<=0 || dep[v]!=-1) continue; 
					dep[v]=dep[u]+1; q.push(v); 
				}
			}
			return dep[T]!=-1; 
		}
		int dfs(int x, int w) {
			if(x==T) return w;
			if(!w) return 0; 
			int ans=0, s; 
			for(int &i=h[x]; i; i=d[i].n) {
				int y=d[i].y, z=d[i].z;  
				if(dep[y]!=dep[x]+1) continue; 
				if(z<=0) continue; 
				s=dfs(y, min(w, z)); ans+=s; w-=s; 
				d[i].z-=s; d[i^1].z+=s; 
				if(!w) break;  
			}
			return ans; 
		}
		int flow(int SS, int TT) {
			S=SS; T=TT; H=h; 
			while(bfs()) ans+=dfs(S, 1e18); 
			return ans; 
		}
	}; 	
	#undef int
}
using namespace Flow; 
int n, m, i, j, k, S, T, TT;
vector<int>G[N], Ge[N]; 
int c[N], p[N], dfn[N], low[N], col[N], pan[N]; 
int vis[N][N], tot, tott, x, y, ans, cnt, shu[N], pp[N]; 
char str[N]; 
stack<int>z; 

void init() {
	for(i=0; i<=150; ++i) G[i].clear(), Ge[i].clear(); 
	memset(c, 0, sizeof(c)); 
	memset(p, 0, sizeof(p)); 
	memset(dfn, 0, sizeof(dfn)); 
	memset(low, 0, sizeof(low)); 
	memset(col, 0, sizeof(col)); 
	memset(vis, 0, sizeof(vis)); 
	memset(shu, 0, sizeof(shu)); 
	memset(pp, 0, sizeof(pp)); 
	tott=0; 
}

void dfs(int x) {
//	debug("> %d %c\n", x, x); 
	dfn[x]=low[x]=++tott; z.push(x); 
	for(int y : G[x]) {
		if(dfn[y]==-1) continue; 
		if(!dfn[y]) dfs(y), low[x]=min(low[x], low[y]); 
		else low[x]=min(low[x], dfn[y]); 
	}
	if(dfn[x]==low[x]) {
//		debug("tot : %d\n", tot); 
		++tot; 
		while(z.top()!=x) col[z.top()]=tot, dfn[z.top()]=-1, z.pop(); 
		col[z.top()]=tot, z.pop(); 
		dfn[x]=-1; 
	}
//	dfn[x]=-1; 
}

void dfs2(int x, int st) {
	vis[st][x]=1; pan[x]=1; 
//	debug("%d <=> %d\n", x, st); 
	for(int y : Ge[x]) {
		if(pan[y]) continue; 
		dfs2(y, st); 
	}
}

signed main()
{
//	freopen("machine.in", "r", stdin);
//	  freopen("machine.out", "w", stdout);
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
	TT=read();
	while(TT--) {
		init(); 
		scanf("%s", str+1); m=read(); 
		for(i=1; str[i]; ++i) c[str[i]]++; 
		for(i=k=0; i<=128; ++i) if(c[i]) ++k; //k为种类 
		n=k; debug("n : %lld\n", n); 
		for(i=1; i<=m; ++i) {
			scanf("%s", str+1); x=str[1]; y=str[2]; 
//			swap(x, y); 
//			printf("%c %c\n", x, y); 
//			if(!c[x]) continue; 
			G[x].pb(y); p[x]=p[y]=1; 
			if(c[x]) pp[x]=1; 
		}
		mf_graph Gow; Gow.reset(600); tott=tot=0; S=599; T=S-1; 
		for(i=0; i<=128; ++i) if(p[i] && !dfn[i]) {
			dfs(i); //debug(">> %lld\n", i); 
		}
		for(i=0; i<=128; ++i) if(p[i] || c[i]) debug("%c %d %d %d | %d\n", i, c[i], p[i], pp[i], col[i]); 
//		for(i=0; i<=128; ++i) if(p[i] && c[i] && !pp[i]) --n; 
	
//		printf("tot : %d | %d\n", tot, n); 
		for(x=0; x<=128; ++x) if(p[x]) {
			for(int y : G[x]) if(col[x]!=col[y]) {
//				printf("# (%d %d) %d -> %d\n", x, y, col[x], col[y]); 
				Ge[col[x]].pb(col[y]); 
			}
		}
//		continue; 
		for(i=1; i<=128; ++i) {
			if(pp[i]) shu[col[i]]|=1; 
			if(c[i]) shu[col[i]]|=2; 
		}
		for(i=1, cnt=0; i<=tot; ++i) {
//			debug("shu[%d] = %d\n", i, shu[i]); 
			if((shu[i]&1)==0) continue; 
			memset(pan, 0, sizeof(pan)); 
			dfs2(i, i); ++cnt; 
			debug("Kuai : %d\n", i); 
			for(j=1; j<=tot; ++j) 
				if(vis[i][j]) {
					if(i==j) continue; 
					if((shu[j]&1)==1 && (shu[j]&2)==0) continue; 
					if((shu[j]&1)==0) continue; 
//					printf("%d %d\n", i, j); 
					Gow.add_edge(i, j+150, 1); 
//					Gow.add_edge(j, i+150, 1); 
				}
			for(j=0; j<=128; ++j) 
				if(p[j] && !c[j] && vis[i][col[j]]) {
					debug("Col %d -> %d\n", i, j); 
					Gow.add_edge(i, j+300, 1); 
				}
		}
		debug("cnt : %d\n", cnt); 
		for(i=0; i<150; ++i) Gow.add_edge(S, i, 1); 
		for(i=151; i<=500; ++i) Gow.add_edge(i, T, 1); 
		ans=Gow.flow(S, T); 
		debug("ans1 : %d\n", ans); 	
		ans=cnt-ans; 
		debug("ans2 : %d\n", ans); 	
		ans=n-ans; 
		printf("%d\n", ans); 	
	}

	return 0;
}


在这里插入图片描述