codeforce每日一题链接

题目链接

题目分数：1400

题目描述

输入$n(2<n<=100) m(1<m≤100)$表示一个$n$点$m$边的无向图，节点编号从$1$到$n$.然后输入$m$条边，每条边输入$v w c(1<c<=m)$，表示有条颜色为$c$的边连接$v$和$w$.然后输入$q(1≤q<=100)$和$q$个询问，每个询问输入$v, w$，你需要输出有多少种颜色$c$满足:从$v$到$w$存在一条路径，这条路径上的边均为颜色$c$。

样例

输入样例1

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

输出样例1

2
1
0

输入样例2

5 7
1 5 1
2 5 1
3 5 1
4 5 1
1 2 2
2 3 2
3 4 2
5
1 5
5 1
2 5
1 5
1 4

输出样例2

1
1
1
1
2

算法1

(并查集) $O(n^3)$

我们可以在每次询问中暴力枚举颜色的种类，在枚举所有的边，把当前枚举的颜色的边的两个端点合并，最后判断询问的两个点是否在一个集合就好，在一个集合里，答案加一。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 110, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int p[N];

inline int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<tuple<int,int,int>> edge;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        edge.pd({a, b, c});
    }

    int q;
    cin>>q;
    while(q--)
    {
        int res = 0;
        int x, y;
        cin>>x>>y;
        for(int i=1;i<=m;i++) // 枚举颜色
        {
            for(int j=1;j<=n;j++) p[j] = j;  //  初始化并查集
            for(auto [a, b, c]:edge){  //  枚举边，将颜色为i的边上的两个点合并
                if(c==i){
                    if(find(p[a]) != find(p[b])) p[find(p[a])] = find(p[b]);
                }
            }
            if(find(p[x]) == find(p[y])) res++;
        }
        cout<<res<<endl;
    }

    return 0;
}

算法2

(dfs) $O(n^3)$

还是暴力枚举颜色的种类，不过这次不用并查集了，换成了深搜。从起始点开始，枚举它的边，如果边的颜色为当前枚举的颜色，就$dfs$下去，否则return false。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 110, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int e[M], ne[M], w[M], h[N], idx;
bool st[N];

inline void add(int a, int b, int c)
{
    e[idx]=b, ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

inline bool dfs(int u, int b, int c)
{
    if(u==b) return true;
    st[u] = true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j = e[i];
        if(st[j]) continue;
        if(w[i]!=c) continue;
        if(dfs(j, b, c)) return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    memset(h, -1, sizeof h);
    cin>>n>>m;

    for(int i=0;i<m;i++){
        int a, b, c;
        cin>>a>>b>>c;
        add(a, b, c), add(b, a, c);
    }

    int q;
    cin>>q;
    while(q--)
    {
        int a, b;
        cin>>a>>b;
        int res = 0;
        for(int i=1;i<=m;i++)  //  枚举颜色
        {
            memset(st, 0, sizeof st);
            if(dfs(a, b, i)) res++;
        }
        cout<<res<<endl;
    }

    return 0;
}

算法3

(并查集) $O(m*log(m)*q)$

对于每种颜色，创建一个新的图形，该图形由颜色的边和由边连接的顶点组成。为每个图形创建 并查集，可以使用它检查一种颜色是否连接顶点 $A$ 和 $B$。对于每个查询，找到一个度数较小的顶点(让这个顶点 $A$ 和另一个顶点 $B$)对于每种颜色，颜色的边连接到 $A$，检查 $A$ 和 $B$ 是否通过颜色连接。说的更直白一点，就是离散化掉每一个点和其对应颜色，这样就处理了不同的颜色、不同的点唯一的对应一个值，在并查集中，就可以直接询问两个点是否用有一种颜色相连，用$map$存下来，之后如果在遇到直接输出就好。
这种做法与牛客网上这道题很像嘤嘤的闺蜜，这是这道题的代码。

C++ 代码

//  https://www.acwing.com/blog/content/34755/

#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<PII,int> PIII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;

const int N = 1e5+10, M = N * 2, INF = 0x3f3f3f3f;

int n, m;
int s[N];
vector<PII> w[N];
vector<int> g[N];
vector<PIII> f;
int cnt;
int p[M];

int get(int a, int c)  //  a是点，c是颜色
{
    return s[a-1] + lower_bound(all(g[a]), c) - g[a].begin();
}

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

bool check(int c,int x)
{
    int l=0,r=g[x].size()-1;
    while(l<r){
        int mid=l+r>>1;
        if(g[x][mid]<c) l=mid+1;
        else r=mid;
    }
    return g[x][r] == c;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a, b, c;
        cin>>a>>b>>c;
        g[a].pd(c);g[b].pd(c);
        f.pd({{a, b}, c});
    }

    for(int i=1;i<=n;i++){
        sort(all(g[i]));
        g[i].erase(unique(all(g[i])), g[i].end());
        s[i] = s[i-1] + g[i].size();
    }

    for(int i=1;i<=s[n];i++) p[i] = i;
    for(int i=0;i<m;i++){
        int a = get(f[i].fi.fi, f[i].se), b = get(f[i].fi.se, f[i].se);
        if(find(p[a])!=find(p[b])) p[find(a)] = find(b);
    }

    int q;
    cin>>q;
    map<PII,int> ma;
    while(q--)
    {
        int a, b;
        cin>>a>>b;
        if(g[a].size()>g[b].size()) swap(a, b);
        if(ma.count({a, b})) cout<<ma[{a, b}]<<endl;
        else{
            int res = 0;
            for(int i=0;i<g[a].size();i++){
                if(!check(g[a][i], b)) continue;
                int x = get(a, g[a][i]), y = get(b, g[a][i]);
                if(find(p[x]) == find(p[y])) res++;
            }
            ma[{a, b}] = res;
            cout<<res<<endl;
        }
    }

    return 0;
}