免费申请网站,徐州网站设计网,大连网站策划,盟族网站建设http://cplusoj.com/d/senior/p/SS231114D
重新梳理一下题目
我们先建图 x → y x\to y x→y#xff0c;然后对点分类#xff1a;原串出现点#xff0c;原串未出现点。
假如我们对一个原串出现点进行了操作#xff0c;那么它剩余所有出边我们立刻去操作必然没有影响。所…http://cplusoj.com/d/senior/p/SS231114D
重新梳理一下题目
我们先建图 x → y x\to y x→y然后对点分类原串出现点原串未出现点。
假如我们对一个原串出现点进行了操作那么它剩余所有出边我们立刻去操作必然没有影响。所以我们只要所有原串出现点都操作一遍即可如果有出边那么我们就把边问题变成了点问题。
考虑一次置换过程抽象为原串上的一条链那必然会造成一个损失。而要消除这个损失一个方法是使链的尾端为原串未出现点。
对于图上路径问题我们可以直接缩点因为一个强连通里我们必然可以从一个进一个出。最后变成了一个DAG。
这就变成了一个二分图问题。每个点可以向其连通的点连边只要满足这个点还有出度或者这个点为原串未出现点。
而左边为匹配的点就是代价了。
#includebits/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 x0,f1;char chgetchar(); while(ch0||
ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){
x(x1)(x3)(ch^48);chgetchar();}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 longstruct mf_graph {struct node {int x, y, z, n; }; vectornoded; vectorinth, H, dep; queueintq; int k; int u, v, w, S, T, ans0; void reset(int n) {h.resize(n5); k1; d.resize(2); H.resize(n5); dep.resize(n5); }void cun(int x, int y, int z) {k; d.pb({x, y, z, h[x]}); d[k].nh[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); hH; dep[S]1; q.push(S); while(!q.empty()) {uq.front(); q.pop(); for(int gh[u]; g; gd[g].n) {vd[g].y; wd[g].z; if(w0 || dep[v]!-1) continue; dep[v]dep[u]1; q.push(v); }}return dep[T]!-1; }int dfs(int x, int w) {if(xT) return w;if(!w) return 0; int ans0, s; for(int ih[x]; i; id[i].n) {int yd[i].y, zd[i].z; if(dep[y]!dep[x]1) continue; if(z0) continue; sdfs(y, min(w, z)); anss; w-s; d[i].z-s; d[i^1].zs; if(!w) break; }return ans; }int flow(int SS, int TT) {SSS; TTT; Hh; while(bfs()) ansdfs(S, 1e18); return ans; }}; #undef int
}
using namespace Flow;
int n, m, i, j, k, S, T, TT;
vectorintG[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];
stackintz; void init() {for(i0; i150; 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)); tott0;
}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 LOCALfreopen(in.txt, r, stdin);freopen(out.txt, w, stdout);#endifTTread();while(TT--) {init(); scanf(%s, str1); mread(); for(i1; str[i]; i) c[str[i]]; for(ik0; i128; i) if(c[i]) k; //k为种类 nk; debug(n : %lld\n, n); for(i1; im; i) {scanf(%s, str1); xstr[1]; ystr[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); totttot0; S599; TS-1; for(i0; i128; i) if(p[i] !dfn[i]) {dfs(i); //debug( %lld\n, i); }for(i0; i128; i) if(p[i] || c[i]) debug(%c %d %d %d | %d\n, i, c[i], p[i], pp[i], col[i]);
// for(i0; i128; i) if(p[i] c[i] !pp[i]) --n; // printf(tot : %d | %d\n, tot, n); for(x0; x128; 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(i1; i128; i) {if(pp[i]) shu[col[i]]|1; if(c[i]) shu[col[i]]|2; }for(i1, cnt0; itot; 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(j1; jtot; j) if(vis[i][j]) {if(ij) 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, j150, 1);
// Gow.add_edge(j, i150, 1); }for(j0; j128; j) if(p[j] !c[j] vis[i][col[j]]) {debug(Col %d - %d\n, i, j); Gow.add_edge(i, j300, 1); }}debug(cnt : %d\n, cnt); for(i0; i150; i) Gow.add_edge(S, i, 1); for(i151; i500; i) Gow.add_edge(i, T, 1); ansGow.flow(S, T); debug(ans1 : %d\n, ans); anscnt-ans; debug(ans2 : %d\n, ans); ansn-ans; printf(%d\n, ans); }return 0;
}
