Solution:
并查集暴力搞。
挺像kruskal找最小生成树的,按边权从小到大排序,枚举最小边,然后不停的加比这条边大的边,直到s,t连通。
#include#define N 505#define M 5005using 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 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"< =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<