http://cplusoj.com/d/senior/p/SS231114D
重新梳理一下题目
我们先建图
x
→
y
xto y
x→y，然后对点分类：原串出现点，原串未出现点。
假如我们对一个原串出服务器托管网现点进行了操作，那么它剩余所有出边我们立刻去操作必然没有影响。所以我们只要所有原串出现点都操作一遍即可（如果有出边），那么我们就把边问题变成了点问题。
考虑一次置换过程抽象为原串上的一条链，那必然会造成一个损失。而要消除这个损失，一个方法是使链的尾端为原串未出现点。
对于图上路径问题，我们可以直接缩点，因为一个强连通里，我们必然可以从一个进一个出。最后变成了一个DAG。
这就变成了一个二分图问题。每个点可以向其连通的点连边，只要满足这个点还有出度，或者这个点为原串未出现点。
而左边为匹配的点就是代价了。
#include
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=(x1)+(x3)+(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;
};
vectornode>d;
vectorint>h, H, dep;
queueint>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 %lldn", 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(w0 || 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(z0) 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;
vectorint>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];
stackint>z;
void init() {
for(i=0; 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));
tott=0;
}
void dfs(int x) {
// debug("> %d %cn", 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 : %dn", 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 %dn", 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; i128; ++i) if(c[i]) ++k; //k为种类
n=k; debug("n : %lldn", n);
for(i=1; im; ++i) {
scanf("%s", str+1); x=str[1]; y=str[2];
// swap(x, y);
// printf("%c %cn", 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; i128; ++i) if(p[i] && !dfn[i]) {
dfs(i); //debug(">> %lldn", i);
}
for(i=0; i128; ++i) if(p[i] || c[i]) debug("%c %d %d %d | %dn", i, c[i], p[i], pp[i], col[i]);
// for(i=0; i
// printf("tot : %d | %dn", tot, n);
for(x=0; x128; ++x) if(p[x]) {
for(int y : G[x]) if(col[x]!=col[y]) {
// printf("# (%d %d) %d -> %dn", x, y, col[x], col[y]);
Ge[col[x]].pb(col[y]);
}
}
// continue;
for(i=1; i128; ++i) {
if(pp[i]) shu[col[i]]|=1;
if(c[i]) shu[col[i]]|=2;
}
for(i=1, cnt=0; itot; ++i) {
// debug("shu[%d] = %dn", i, shu[i]);
if((shu[i]&1)==0) continue;
memset(pan, 0, sizeof(pan));
dfs2(i, i); ++cnt;
debug("Kuai : %dn", i);
for(j=1; jtot; ++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 %dn", i, j);
服务器托管网 Gow.add_edge(i, j+150, 1);
// Gow.add_edge(j, i+150, 1);
}
for(j=0; j128; ++j)
if(p[j] && !c[j] && vis[i][col[j]]) {
debug("Col %d -> %dn", i, j);
Gow.add_edge(i, j+300, 1);
}
}
debug("cnt : %dn", cnt);
for(i=0; i150; ++i) Gow.add_edge(S, i, 1);
for(i=151; i500; ++i) Gow.add_edge(i, T, 1);
ans=Gow.flow(S, T);
debug("ans1 : %dn", ans);
ans=cnt-ans;
debug("ans2 : %dn", ans);
ans=n-ans;
printf("%dn", ans);
}
return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
点云处理 第一章 点云数据采集 1.点云配准 点云配准是将两个或多个点云数据集融合到一个统一的坐标系统中的过程。这通常是为了创建一个完整的模型或融合从不同视角采集的数据。 点云配准一般分为粗配准和精配准，粗配准指的是在两幅点云之间的变换完全未知的情况下进行较为…
