洛谷1550 打井

洛谷1550 打井
找一个数组来存以x为根的树的最小值，所有边按从小到大排序，
如果e[i].v<=Min[t1]||....(见代码
  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(int i=a;i<=b;i++)
 18 #define p(a) putchar(a)
 19 #define g() getchar()
 20 
 21 using namespace std;
 22 
 23 int n,x,cnt,num;
 24 int a[310];
 25 int b[310][310];
 26 int d[310],Min[310];
 27 int ans;
 28 
 29 struct kru{
 30     int l;
 31     int r;
 32     int v;
 33     bool operator < (const kru &temp)const{
 34         return v<temp.v;
 35     }
 36 }e[90010];
 37 
 38 void in(int &x){
 39     int y=1;
 40     char c=g();x=0;
 41     while(c<'0'||c>'9'){
 42         if(c=='-')y=-1;
 43         c=g();
 44     }
 45     while(c<='9'&&c>='0'){
 46         x=(x<<1)+(x<<3)+c-'0';c=g();
 47     }
 48     x*=y;
 49 }
 50 void o(int x){
 51     if(x<0){
 52         p('-');
 53         x=-x;
 54     }
 55     if(x>9)o(x/10);
 56     p(x%10+'0');
 57 }
 58 
 59 int find(int x){
 60     if(d[x]==x)return x;
 61     return d[x]=find(d[x]);
 62 }
 63 
 64 int main(){
 65     in(n);
 66     For(i,1,n){
 67         d[i]=i;
 68         in(a[i]);
 69         Min[i]=a[i];
 70     }
 71     For(i,1,n)
 72         For(j,1,n){
 73             in(x);
 74             if(i<j){
 75                 e[++cnt].l=i;
 76                 e[cnt].r=j;
 77                 e[cnt].v=x;
 78             }
 79         }
 80     sort(e+1,e+cnt+1);
 81     For(i,1,cnt){
 82         int t1=find(e[i].l);
 83         int t2=find(e[i].r);
 84         if(t1!=t2&&e[i].v<=max(Min[t1],Min[t2])){
 85             if(e[i].v<=Min[t1]&&e[i].v>=Min[t2]){
 86                 Min[t1]=Min[t2];
 87                 ans+=e[i].v;
 88                 d[t1]=t2;
 89             }
 90             else 
 91                 if(e[i].v>=Min[t1]&&e[i].v<=Min[t2]){
 92                 Min[t2]=Min[t1];
 93                 ans+=e[i].v;
 94                 d[t2]=t1;
 95             }
 96             else
 97                 if(e[i].v<min(Min[t1],Min[t2])){
 98                     if(Min[t1]>=Min[t2]){
 99                         Min[t1]=Min[t2];
100                         ans+=e[i].v;
101                         d[t1]=t2;
102                     }
103                     else{
104                         Min[t2]=Min[t1];
105                         ans+=e[i].v;
106                         d[t2]=t1;
107                     }
108                 }
109                 num++;
110         }
111         if(num==n-1)break;
112     }
113     For(i,1,n)
114         if(d[i]==i)
115             ans+=a[i];
116     o(ans);
117     return 0;
118 }
View Code