题目链接【https://nanti.jisuanke.com/t/27647】
//计蒜客2018复赛D题,想简单了。
题解:
题目是中文的,不再赘述。
题解:
分为三种情况:1、两个字符串都不能变:这种情况最简单,直接暴力判断两个支付穿是否相同即可。
2、两个字符串都能变:把上下对应位置不同的点连无向边(因为都可以改变),建立了一个深林,这里用并查集实现,顺便维护每个联块的大小,对于每个联通块来说,要把这些点都变成一样的,最少要变换(size-1)次,即选出一个点,把其他的点都变成被选中的点。
3、一个能变,一个不能变:这种情况最复杂。同第二种情况,这里需要建图,建立单向边,(只能由V变成C),对于每一个联通块,我们判断该联通块是不是DAG,如果是,那么只需要改变(size-1)次就行了。如果不是DAG,那么联通块中存在环,那么最少要变(size)次,只需要把这些点连接成有向环就可以了,保证了两两可以互达。
只是思路、具体细节和原因需要自己思考。欢迎斧正。QQ2421780543。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 15;
LL a[maxn], b[maxn];
char s[15], t[15];
//-----------------------并查集
int fa[maxn], val[maxn];
void init()
{
for(int i = 1; i <= 100000; i++)
fa[i] = i, val[i] = 1;
}
int Find(int u)
{
if(fa[u] == u)
return u;
return fa[u] = Find(fa[u]);
}
void Unit(int u, int v)
{
int x = Find(u);
int y = Find(v);
if(x != y)
{
fa[x] = y;
val[y] += val[x];
val[x] = 0;
}
}
//-------------------------EDGE
int rd[maxn], vis[maxn], cnt = 0;;
vector<int>vt[maxn];
map<int, int>mp;
queue<int>que;
struct Edge
{
int to, next;
Edge(int to = 0, int next = 0): to(to), next(next) {}
} E[maxn * 4];
int head[maxn], tot;
void Init_Edge()
{
for(int i = 1; i <= 100000; i++)
head[i] = -1;
tot = 0;
}
void Add_Edge(int u, int v)
{
E[tot] = Edge(v, head[u]);
head[u] = tot++;
}
//--------------------------主函数
int main ()
{
int n, fg1 = 0, fg2 = 0;
scanf("%d", &n);
scanf("%s", s);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
scanf("%s", t);
for(int i = 1; i <= n; i++)
scanf("%lld", &b[i]);
if(s[0] == 'V')
fg1 = 1;
if(t[0] == 'V')
fg2 = 1;
if((!fg1) && (!fg2))//都不能更改
{
bool ans = true;
for(int i = 1; i <= n && ans; i++)
if(a[i] != b[i])
ans = false;
if(ans)
printf("0\n");
else
printf("-1\n");
}
else if(fg1 && fg2)//都可以更改
{
init();
for(int i = 1; i <= n; i++)
{
if(a[i] != b[i])
Unit(a[i], b[i]);
}
int num = 0;
for(int i = 1; i <= 100000; i++)
{
Find(i);
if(fa[i] == i)
num += val[i] - 1;
}
printf("%d\n", num);
}
else //只能改一个
{
init();
Init_Edge();
for(int i = 1; i <= n; i++)
if(a[i] != b[i])
{
Unit(a[i], b[i]);
Add_Edge(a[i], b[i]);
rd[b[i]] ++;
vis[a[i]] = vis[b[i]] = 1;
}
for(int i = 1; i <= 100000; i++)//提取联通块
{
if(vis[i])
{
int t = Find(i);
if(mp[t])
{
int tmp = mp[t];
vt[tmp].push_back(i);
}
else
{
mp[t] = ++cnt;
vt[cnt].push_back(i);
}
}
}
int num = 0;
for(int i = 1; i <= cnt; i++)//拓扑排序,判断DAG
{
int len = vt[i].size();
for(int j = 0; j < len; j++)
{
int tmp = vt[i][j];
if(rd[tmp] == 0)
que.push(tmp);
}
int tmp = 0;
while(!que.empty())
{
int u = que.front();
que.pop();
tmp++;
for(int j = head[u]; j != -1; j = E[j].next)
{
int v = E[j].to;
rd[v]--;
if(rd[v] == 0)
que.push(v);
}
}
if(tmp == len)
num += len - 1;
else
num += len;
}
printf("%d\n", num);
}
return 0;
}
原文链接: https://www.cnblogs.com/pealicx/p/9194750.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/276238
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!