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;
}