感觉逻辑上有很大问题QwQ
by VeritasatireV @ 2019-07-13 16:23:34
刚学OI就做这题。
我要从1楼跳下去
by _Felix @ 2019-07-13 16:26:33
~~怎么感觉我比萌新还新~~
by EаrringYYR @ 2019-07-13 16:28:01
```cpp
#include<bits/stdc++.h>
using namespace std;
const int Max=1000010;
struct node{
int f;
int l;
int num;
}edge[Max];
int fa[Max];
int n,m,st,ed;
void CL(){for(int i=1;i<=n;i++) fa[i]=i;}
int findfa(int x){return fa[x]==x ? x : fa[x]=findfa(fa[x]);}
void mergefa(int a,int b) {int t1=findfa(a),t2=findfa(b); if(t1!=t2) fa[t2]=t1;}
bool cmp(node a,node b) {return a.num>b.num;}
int gcd(int a,int b){
return a%b==0 ? b : gcd(b,a%b);
}
signed main(){
cin>>n>>m;
CL();
for(int i=1;i<=m;i++)
cin>>edge[i].f>>edge[i].l>>edge[i].num;
sort(edge+1,edge+m+1,cmp);
cin>>st>>ed;
int Enum=0,tmp=1;
while(1==1)
{
if(findfa(st)==findfa(ed)){
int nm=gcd(edge[1].num,edge[tmp-1].num);
if(edge[1].num%edge[tmp-1].num==0) cout<<edge[1].num/edge[tmp-1].num;
else cout<<edge[1].num/nm<<'/'<<edge[tmp-1].num/nm;
return 0;
}
if(Enum==m&&findfa(st)!=findfa(ed)) {
cout<<"IMPOSSIBLE";
return 0;
}
if(findfa(edge[tmp].f)!=findfa(edge[tmp].l)){
mergefa(edge[tmp].f,edge[tmp].l);
Enum++;
}
tmp++;
}
return 0;
}
```
by Smile_Cindy @ 2019-07-13 16:29:06
我怀疑你不是妹子,但我没有证据
by Smile_Cindy @ 2019-07-13 16:29:30
~~然而楼上并没有改啊~~
(应该是我眼瞎)
(为什么怀疑我的性别QAQ)
by VeritasatireV @ 2019-07-13 16:33:17
```
#include<bits/stdc++.h>
using namespace std;
const int Max=1000010;
struct node{
int f;
int l;
int num;
}edge[Max];
int fa[Max];
int n,m,st,ed;
void CL(){for(int i=1;i<=n;i++) fa[i]=i;}
int findfa(int x){return fa[x]==x ? x : fa[x]=findfa(fa[x]);}
void mergefa(int a,int b) {int t1=findfa(a),t2=findfa(b); if(t1!=t2) fa[t2]=t1;}
bool cmp(node a,node b) {return a.num>b.num;}
int gcd(int a,int b){
return a%b==0 ? b : gcd(b,a%b);
}
signed main(){
cin>>n>>m;
CL();
for(int i=1;i<=m;i++)
cin>>edge[i].f>>edge[i].l>>edge[i].num;
sort(edge+1,edge+m+1,cmp);
cin>>st>>ed;
int Enum=0,tmp=1;
double ans=1E9,ansx,ansy;
bool pd=false;
for(int i=1;i<=m;i++){
CL();
for(int j=i;j<=m;j++){
if(findfa(i)==findfa(j)){
if(ans<(double)edge[i].num/edge[j].num)
ans=.....,ansx=.....,ansy=.....;
pd=true;
break;
}
else{
mergefa(.....);
}
}
cout<<ansx/gcd(ansx,ansy)<<"/"<<ansy/gcd(ansx,ansy)<<endl;
return 0;
}
```
by EаrringYYR @ 2019-07-13 16:51:50
主要是这道题需要判断对于以每条边当作最大边是的答案来更新ans,而你只考虑了以第一条边作为最大边的情况
by EаrringYYR @ 2019-07-13 16:53:17
漏了
```
if(!pd){
cout<<"IMPOSSIBLE";
return 0;
}
by EаrringYYR @ 2019-07-13 16:54:39
@[Bro——Sea](/space/show?uid=225253) 巨佬虐萌新
我好菜啊
by VeritasatireV @ 2019-07-13 16:54:41