P2502 [HAOI2006]旅行

P2502 [HAOI2006]旅行
有些问题光靠直觉是不靠谱的，必须有简单的证明，要么就考虑到所有情况。
这个题我想的是要么见最小生成树，要么建最大生成树，哎，我sb了
一种很简单的情况就能卡掉
在最小生成树中，Min为a,它有重边，b比a大，而且b依然是Min，那么此时答案就会更优。
正解就是枚举每一个边（从大到小），然后加边，直到联通，不断更新答案
时间复杂度为O（m^2)

这是一开始的错误代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<ctime>
  7 #include<set>
  8 #include<map>
  9 #include<stack>
 10 #include<cstring>
 11 #define inf 2147483647
 12 #define ls rt<<1
 13 #define rs rt<<1|1
 14 #define lson ls,nl,mid,l,r
 15 #define rson rs,mid+1,nr,l,r
 16 #define N 100010
 17 #define For(i,a,b) for(register long long i=a;i<=b;i++)
 18 #define p(a) putchar(a)
 19 #define g() getchar()
 20 
 21 using namespace std;
 22 
 23 long long n,m;
 24 long long x,y,v;
 25 long long s,t,Max,Min,cnt;
 26 bool vis[510];
 27 long long ans[10];
 28 long long d[510];
 29 bool flag;
 30 
 31 struct node{
 32     long long n;
 33     long long v;
 34     node *next;
 35 }*e[5010];
 36 
 37 struct kru{
 38     long long l;
 39     long long r;
 40     long long v;
 41 }E[5010];
 42 
 43 void in(long long &x){
 44     long long y=1;
 45     char c=g();x=0;
 46     while(c<'0'||c>'9'){
 47         if(c=='-')y=-1;
 48         c=g();
 49     }
 50     while(c<='9'&&c>='0'){
 51         x=(x<<1)+(x<<3)+c-'0';c=g();
 52     }
 53     x*=y;
 54 }
 55 void o(long long x){
 56     if(x<0){
 57         p('-');
 58         x=-x;
 59     }
 60     if(x>9)o(x/10);
 61     p(x%10+'0');
 62 }
 63 
 64 bool cmp1(kru a,kru b){
 65     return a.v<b.v;
 66 }
 67 
 68 bool cmp2(kru a,kru b){
 69     return a.v>b.v;
 70 }
 71 
 72 void push(long long x,long long y,long long v){
 73     node *p;
 74     p=new node();
 75     p->n=y;
 76     p->v=v;
 77     if(e[x]==NULL)
 78         e[x]=p;
 79     else{
 80         p->next=e[x]->next;
 81         e[x]->next=p;
 82     }
 83 }
 84 
 85 long long find(long long x){
 86     if(d[x]==x)return x;
 87     return d[x]=find(d[x]);
 88 }
 89 
 90 void build1(){
 91     For(i,1,n)
 92         d[i]=i;
 93     For(i,1,m){
 94         long long t1=find(E[i].l);
 95         long long t2=find(E[i].r);
 96         if(d[t1]!=d[t2]){
 97             d[t1]=t2;
 98         }
 99     }
100 }
101 
102 void build2(){
103     For(i,1,n)
104         e[i]=NULL;
105     For(i,1,m){
106         if(d[E[i].l]==d[E[i].r]){
107             push(E[i].l,E[i].r,E[i].v);
108             push(E[i].r,E[i].l,E[i].v);
109         }
110     }
111 }
112 
113 void dfs(long long now,long long Max,long long Min){
114     if(now==t){
115         For(i,2,15000){
116             if(Max%i==0&&Min%i==0){
117                 Max/=i;
118                 Min/=i;
119             }
120         }
121         ans[++cnt]=Max;ans[++cnt]=Min;
122         flag=true;
123         return;
124     }
125      for(register node *i=e[now];i;i=i->next){
126         if(!vis[i->n]){
127             vis[i->n]=true;
128             dfs(i->n,max(Max,i->v),min(Min,i->v));
129             vis[i->n]=false;
130         }
131         if(flag)return;
132     }
133 }
134 
135 int main(){
136     in(n);in(m);
137     For(i,1,m){
138         in(x);in(y);in(v);
139         E[i].l=x;
140         E[i].r=y;
141         E[i].v=v;
142     }
143     in(s);in(t);
144     //跑最小生成树
145     sort(E+1,E+m+1,cmp1);
146     build1();
147     For(i,1,n)
148         d[i]=find(d[i]);
149     if(d[s]!=d[t]){
150         cout<<"IMPOSSIBLE";
151         return 0;
152     }
153     build2();
154     flag=false;
155     dfs(s,-inf,inf);
156 
157     sort(E+1,E+m+1,cmp2);
158     build1();
159     For(i,1,n)
160         d[i]=find(d[i]);
161     build2(); 
162     For(i,1,n)
163         vis[i]=false;
164     flag=false;
165     dfs(s,-inf,inf);
166     // For(i,1,cnt){
167     //     o(ans[i]);p('
');
168     // }
169 
170     if(cnt==2||double(ans[1])/double(ans[2])<=double(ans[3])/double(ans[4])){
171         if(ans[1]%ans[2]==0)
172             o(ans[1]/ans[2]);
173         else
174             cout<<ans[1]<<"/"<<ans[2];
175     }
176     else
177         if(ans[3]%ans[4]==0)
178             o(ans[3]/ans[4]);
179         else
180             cout<<ans[3]<<"/"<<ans[4];
181     return 0;
182 }

View Code

对了30分

正解:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<ctime>
  7 #include<set>
  8 #include<map>
  9 #include<stack>
 10 #include<cstring>
 11 #define inf 2147483647
 12 #define ls rt<<1
 13 #define rs rt<<1|1
 14 #define lson ls,nl,mid,l,r
 15 #define rson rs,mid+1,nr,l,r
 16 #define N 100010
 17 #define For(i,a,b) for(register int i=a;i<=b;i++)
 18 #define p(a) putchar(a)
 19 #define g() getchar()
 20 
 21 using namespace std;
 22 int n,m;
 23 int d[5010];
 24 int l,r,v;
 25 int s,t;
 26 int x,y,z;
 27 struct kru{
 28     int l;
 29     int r;
 30     int v;
 31     bool operator < (const kru &temp)const{
 32         return v>temp.v;
 33     }
 34 }e[5010];
 35 
 36 
 37 void in(int &x){
 38     int y=1;
 39     char c=g();x=0;
 40     while(c<'0'||c>'9'){
 41         if(c=='-')y=-1;
 42         c=g();
 43     }
 44     while(c<='9'&&c>='0'){
 45         x=(x<<1)+(x<<3)+c-'0';c=g();
 46     }
 47     x*=y;
 48 }
 49 void o(int x){
 50     if(x<0){
 51         p('-');
 52         x=-x;
 53     }
 54     if(x>9)o(x/10);
 55     p(x%10+'0');
 56 }
 57 
 58 int find(int x){
 59     if(d[x]==x)return x;
 60     return d[x]=find(d[x]);
 61 }
 62 
 63 int gcd(int x,int y){
 64     return y==0?x:gcd(y,x%y);
 65 }
 66 
 67 int main(){
 68     in(n);in(m);
 69     For(i,1,m){
 70         in(l);in(r);in(v);
 71         e[i].l=l;e[i].r=r;e[i].v=v;
 72     }
 73     in(s);in(t);
 74     x=inf;y=1;
 75 
 76     sort(e+1,e+m+1);
 77 
 78     For(i,1,m){
 79 
 80         For(ii,1,n)
 81             d[ii]=ii;
 82 
 83         For(j,i,m){
 84 
 85             int t1=find(e[j].l);
 86             int t2=find(e[j].r);
 87             if(t1!=t2)
 88                 d[t1]=t2;
 89             // For(k,1,n)
 90             //     d[k]=find(d[k]);
 91             if(find(s)==find(t)){
 92                 if(double(e[i].v)/double(e[j].v)<double(x)/double(y)){
 93                 //    cout<<double(e[i].v)/double(e[j].v)<<endl;
 94                     x=e[i].v;y=e[j].v;
 95                 }
 96                 break;
 97             }
 98         }
 99     }
100     if(x/y==inf){
101         cout<<"IMPOSSIBLE";
102         return 0;
103     }
104     z=gcd(x,y);
105     x/=z;y/=z;
106     if(x%y==0)
107         o(x/y);
108     else
109         cout<<x<<"/"<<y;
110     return 0;
111 }

View Code