P2502 [HAOI2006]旅行
有些问题光靠直觉是不靠谱的，必须有简单的证明，要么就考虑到所有情况。
这个题我想的是要么见最小生成树，要么建最大生成树，哎，我sb了
一种很简单的情况就能卡掉
在最小生成树中，Min为a,它有重边，b比a大，而且b依然是Min，那么此时答案就会更优。
正解就是枚举每一个边（从大到小），然后加边，直到联通，不断更新答案
时间复杂度为O（m^2)
这是一开始的错误代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,nl,mid,l,r
#define rson rs,mid+1,nr,l,r
#define N 100010
#define For(i,a,b) for(register long long i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar() using namespace std; long long n,m;
long long x,y,v;
long long s,t,Max,Min,cnt;
bool vis[];
long long ans[];
long long d[];
bool flag; struct node{
long long n;
long long v;
node *next;
}*e[]; struct kru{
long long l;
long long r;
long long v;
}E[]; void in(long long &x){
long long y=;
char c=g();x=;
while(c<''||c>''){
if(c=='-')y=-;
c=g();
}
while(c<=''&&c>=''){
x=(x<<)+(x<<)+c-'';c=g();
}
x*=y;
}
void o(long long x){
if(x<){
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} bool cmp1(kru a,kru b){
return a.v<b.v;
} bool cmp2(kru a,kru b){
return a.v>b.v;
} void push(long long x,long long y,long long v){
node *p;
p=new node();
p->n=y;
p->v=v;
if(e[x]==NULL)
e[x]=p;
else{
p->next=e[x]->next;
e[x]->next=p;
}
} long long find(long long x){
if(d[x]==x)return x;
return d[x]=find(d[x]);
} void build1(){
For(i,,n)
d[i]=i;
For(i,,m){
long long t1=find(E[i].l);
long long t2=find(E[i].r);
if(d[t1]!=d[t2]){
d[t1]=t2;
}
}
} void build2(){
For(i,,n)
e[i]=NULL;
For(i,,m){
if(d[E[i].l]==d[E[i].r]){
push(E[i].l,E[i].r,E[i].v);
push(E[i].r,E[i].l,E[i].v);
}
}
} void dfs(long long now,long long Max,long long Min){
if(now==t){
For(i,,){
if(Max%i==&&Min%i==){
Max/=i;
Min/=i;
}
}
ans[++cnt]=Max;ans[++cnt]=Min;
flag=true;
return;
}
for(register node *i=e[now];i;i=i->next){
if(!vis[i->n]){
vis[i->n]=true;
dfs(i->n,max(Max,i->v),min(Min,i->v));
vis[i->n]=false;
}
if(flag)return;
}
} int main(){
in(n);in(m);
For(i,,m){
in(x);in(y);in(v);
E[i].l=x;
E[i].r=y;
E[i].v=v;
}
in(s);in(t);
//跑最小生成树
sort(E+,E+m+,cmp1);
build1();
For(i,,n)
d[i]=find(d[i]);
if(d[s]!=d[t]){
cout<<"IMPOSSIBLE";
return ;
}
build2();
flag=false;
dfs(s,-inf,inf); sort(E+,E+m+,cmp2);
build1();
For(i,,n)
d[i]=find(d[i]);
build2();
For(i,,n)
vis[i]=false;
flag=false;
dfs(s,-inf,inf);
// For(i,1,cnt){
// o(ans[i]);p('\n');
// } if(cnt==||double(ans[])/double(ans[])<=double(ans[])/double(ans[])){
if(ans[]%ans[]==)
o(ans[]/ans[]);
else
cout<<ans[]<<"/"<<ans[];
}
else
if(ans[]%ans[]==)
o(ans[]/ans[]);
else
cout<<ans[]<<"/"<<ans[];
return ;
}
对了30分
正解:
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,nl,mid,l,r
#define rson rs,mid+1,nr,l,r
#define N 100010
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar() using namespace std;
int n,m;
int d[];
int l,r,v;
int s,t;
int x,y,z;
struct kru{
int l;
int r;
int v;
bool operator < (const kru &temp)const{
return v>temp.v;
}
}e[]; void in(int &x){
int y=;
char c=g();x=;
while(c<''||c>''){
if(c=='-')y=-;
c=g();
}
while(c<=''&&c>=''){
x=(x<<)+(x<<)+c-'';c=g();
}
x*=y;
}
void o(int x){
if(x<){
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} int find(int x){
if(d[x]==x)return x;
return d[x]=find(d[x]);
} int gcd(int x,int y){
return y==?x:gcd(y,x%y);
} int main(){
in(n);in(m);
For(i,,m){
in(l);in(r);in(v);
e[i].l=l;e[i].r=r;e[i].v=v;
}
in(s);in(t);
x=inf;y=; sort(e+,e+m+); For(i,,m){ For(ii,,n)
d[ii]=ii; For(j,i,m){ int t1=find(e[j].l);
int t2=find(e[j].r);
if(t1!=t2)
d[t1]=t2;
// For(k,1,n)
// d[k]=find(d[k]);
if(find(s)==find(t)){
if(double(e[i].v)/double(e[j].v)<double(x)/double(y)){
// cout<<double(e[i].v)/double(e[j].v)<<endl;
x=e[i].v;y=e[j].v;
}
break;
}
}
}
if(x/y==inf){
cout<<"IMPOSSIBLE";
return ;
}
z=gcd(x,y);
x/=z;y/=z;
if(x%y==)
o(x/y);
else
cout<<x<<"/"<<y;
return ;
}