1 条题解
-
1
TUPLE+
Answer is HERE!
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> p_t; const int MX=300005; map<p_t, set<int>> d; int n,m,u[MX],v[MX],w[MX]; int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=m;i++){ cin>>u[i]>>v[i]>>w[i]; d[make_pair(u[i],v[i])].insert(w[i]);} int ans=0; for(int i=1;i<=m;i++){ set<int> *W=&d[make_pair(u[i],v[i])], *V=&d[make_pair(u[i],w[i])], *U=&d[make_pair(v[i],w[i])]; if(U->size()>V->size())swap(U,V); if(V->size()>W->size())swap(V,W); if(U->size()>V->size())swap(U,V); // 冒泡排序,找到最小的一个集合,保证求交集复杂度 for(auto j:*U)if(V->find(j)!=V->end()&&W->find(j)!=W->end()){ ans++;}} cout<<ans<<endl; return 0;}
Thant you! With pleasure.
信息
- ID
- 45
- 时间
- 2000ms
- 内存
- 512MiB
- 难度
- 7
- 标签
- 递交数
- 142
- 已通过
- 30
- 上传者