链接:https://ac.nowcoder.com/acm/contest/223/A
来源:牛客网

题目描述

你有一张n个点的完全图(即任意两点之间都有无向边)
现在给出这张图的两棵生成树
定义一次操作为:在任意一棵生成树中删除一条边后再加入一条边(必须在同一棵树中操作),同时需要保证操作完后仍然是一棵树
问使得两棵树相同的最少操作次数,若不存在合法的操作方案,输出-1
注意:这里的相同指的是点集与边集均相同,也就是对于第一棵树中的边(u, v),第二棵树中一定存在边(u, v)或(v, u),再不懂请看样例解释。

输入描述:

一个整数n表示无向图的点数
接下来n - 1行,每行两个整数u, v表示第一棵生成树中的边
再接下来n - 1行,每行两个整数u, v表示第二棵生成树中的边

输出描述:

一个整数,表示最少操作次数

示例1

输入

6
6 1
1 2
2 3
3 5
5 4
1 2
2 4
4 5
5 3
6 4

输出

2

示例2

输入

3
1 2
2 3
1 3
3 2

输出

1

示例3

输入

2
1 2
2 1

输出

0

这个题矩阵没有办法开那么大,所以,STL中的map是一个很好的选择,然后因为给的是两个点的坐标,所以第一个参数可以使用pair来进行构造,也算是第一次使用pair了,挺舒服的。也过了第一个python代码,放在后面。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    map <pair<int,int>,int> mat;
    int n,x,y;cin>>n;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        if(x>y) swap(x,y);
        mat[make_pair(x,y)]=1;
    }
    int ans=0;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        if(x>y) swap(x,y);
        if(mat[make_pair(x,y)]==1)
            continue;
        else
            ans++;
    }
    cout<<ans<<endl;
    //system("pause");
    return 0;
}
n = int(input())
ans = 0
mat = {}
for i in range(n-1):
    x,y = map(int,input().strip().split())
    if(x > y):
        x,y = y,x
    mat[(x,y)] = 1
for i in range(n - 1):
    x,y = map(int,input().strip().split())
    if(x > y):
        x,y = y,x
    if not(mat.get((x,y))):
        ans+=1
print(ans)

发表评论

电子邮件地址不会被公开。 必填项已用*标注