本文主要是介绍1146.相似度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
相似度:
时间限制:1500MS内存限制:128000KB
题目描述
小G通过摆放一些城市和道路构成了一个世界地图。趁着小G出去玩的时候,大G把小G的世界地图上的城市全部打乱并放在了原来这些城市所在的位置(并不是一一对应),又修改了一些道路。小G玩完回来后发现自己的东西被打乱了,感到非常生气,但是他又被一个更有趣的问题吸引了:被修改之后的世界地图与原来的世界地图的最大相似度是多少?
(ps:相似度的定义为将城市还原后还有多少条道路和之前的道路相同)
输入
第一行为两个整数n,m,表示一共有n个城市,m条道路
接下来m行,每行两个整数x,y,表示原来小G的世界地图中有一条道路连接编号为x和y的两个城市。
紧接着m行,每行两个整数x’,y’,表示被大G修改后的世界地图中有一条道路连接编号为x’和y’的两个城市。
输出
一行一个整数,表示最大相似度。
输入样例复制
4 5
4 3
2 1
3 2
2 4
2 3
1 4
3 2
2 1
1 3
4 4
输出样例复制
4
说明
【样例解释】 原图中的1,2,3,4号城市分别对应现在图中的4,1,2,3 将修改后的图还原 1 4->2 1 3 2->4 3 2 1->3 2 1 3->2 4 4 4->1 1 与原图比较发现有4条边是一样的。 【数据规模和约定】 对于30%的数据,1 ≤ n ≤ 3,1 ≤ m≤ 20。 对于60%的数据,1 ≤ n ≤ 7,1 ≤ m≤ 70。 对于100%的数据,1 ≤ n ≤ 9,1 ≤ m≤ 300。
解法:
这一题全排列,,,,之后再一一比较。
程序:
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int ans,z,xx[5001],yy[5001],x,y,s[5001],map[5001][5001],f[1001][1010];
bool p[5001];
int n,m;
void bfs ()
{
ans=0;
int t,tt;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
map[i][j]=f[i][j];
for (int i=1;i<=m;i++)
{
t=s[xx[i]];
tt=s[yy[i]];
if (map[t][tt]>0)
{
map[t][tt]--;
ans+=1;
}
}
z=max(z,ans);
}
void tj (int c)
{
if (c==n)
{
bfs ();
return;
}
for (int i=1;i<=n;i++)
{
if (p[i]==0)
{
s[i]=c+1;
p[i]=1;
tj(c+1);
p[i]=0;
}
}
}
int main()
{
cin>>n>>m;
for (int j=1;j<=m;j++)
{
cin>>x>>y;
map[x][y]++;
f[x][y]++;
}
for (int j=1;j<=m;j++)
cin>>xx[j]>>yy[j];
tj(0);
cout<<z;
}
这篇关于1146.相似度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!