传送门
Solution:
并查集暴力搞。
挺像kruskal找最小生成树的，按边权从小到大排序，枚举最小边，然后不停的加比这条边大的边，直到s，t连通。
#include<bits/stdc++.h> #define N 505 #define M 5005 using namespace std; int n,m,s,t,father[N]; struct node { int from,to,val; }edge[2*M]; inline bool cmp(const node &a,const node &b) { return a.val<b.val; } inline int getfather(int x) { if(father[x]==x) return x; return father[x]=getfather(father[x]); } inline int gcd(int x,int y) { if(y>x) return gcd(y,x); if(!y) return x; return gcd(y,x%y); } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>m; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; edge[i].to=y; edge[i].from=x; edge[i].val=z; } cin>>s>>t; sort(edge+1,edge+m+1,cmp); int ans_max,ans_min; for(int i=1;i<=m;i++) { int j; for(j=1;j<=n;j++) father[j]=j; for(j=i;j<=m;j++) { int ax=getfather(edge[j].from); int bx=getfather(edge[j].to); if(ax!=bx) { father[ax]=bx; if(getfather(s)==getfather(t)) break; } } if(i==1&&getfather(s)!=getfather(t)) { cout<<"IMPOSSIBLE"<<endl; return 0; } if(getfather(s)!=getfather(t)) break; //小小的剪枝 if(ans_max*edge[i].val>=ans_min*edge[j].val){//只是移一下项 ans_max=edge[j].val; ans_min=edge[i].val; } } int a=gcd(ans_max,ans_min); if(a==ans_min) cout<<ans_max/ans_min<<endl; else cout<<ans_max/a<<"/"<<ans_min/a<<endl; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9446294.html
相关资源：各显卡算力对照表！