spanning tree

强联通图：边为 c=v*(v-1)/2

uva,544

kruskal求最大生成树，然后求数边里面最小的限制。用到了剪枝的方法，把字符串映射成整数，然后跑一遍就过了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <sstream>
 6 #include <map>
 7 #include <algorithm>
 8 
 9 using namespace std;
10 const int maxn=205;
11 map<string,int> mp;
12 int val;
13 int start;
14 int tar;
15 int hash[maxn];
16 int pos;
17 int n,r;
18 struct Edge
19 {
20     int u,v;
21     int weight;
22     bool operator<(const Edge& x)const
23     {
24         return weight>x.weight;
25     }
26 }E[maxn*maxn];
27 
28 int parent[maxn];
29 int find(int y)
30 {
31     return y==parent[y]?y:parent[y]=find(parent[y]);
32 }
33 
34 void Kruskal()
35 {
36     for(int i=0;i<pos;i++)
37     {
38         int pa=find(E[i].u);
39         int pb=find(E[i].v);
40         if(pa!=pb)
41             parent[pa]=pb;
42         if(find(start)==find(tar))
43         {
44             val=E[i].weight;
45             return;
46         }
47     }
48 }
49 
50 int main()
51 {
52     int cas=1;
53     string s1,s2;
54     int tmp;
55     while(scanf("%d%d",&n,&r) && n+r)
56     {
57         int cnt=0;
58         pos=0;
59         mp.clear();
60         for(int i=0;i<n;i++)
61             parent[i]=i;
62         for(int i=0;i<r;i++)
63         {
64             cin>>s1>>s2>>tmp;
65             if(!mp[s1])
66                 mp[s1]=cnt++;
67             if(!mp[s2])
68                 mp[s2]=cnt++;
69             E[pos].u=mp[s1];
70             E[pos].v=mp[s2];
71             E[pos++].weight=tmp;
72         }
73         cin>>s1>>s2;
74         start=mp[s1];
75         tar=mp[s2];
76         sort(E,E+r);
77         
78         Kruskal();
79         
80         printf("Scenario #%d
%d tons

",cas++,val);
81     }
82     return 0;
83 }

View Code

uva,10034

注意一下输入，每两个用例之间有换行，但是最后一个用例之后没有换行。。pr了几次

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 const int maxn=105;
 8 int n;
 9 int pos;
10 double result;
11 
12 struct Point
13 {
14     double x,y;
15     void read()
16     {
17         scanf("%lf%lf",&x,&y);
18     }
19 }p[maxn];
20 
21 double dist(Point a,Point b)
22 {
23     double dx=a.x-b.x;
24     double dy=a.y-b.y;
25     return sqrt(dx*dx+dy*dy);
26 }
27 
28 
29 struct Edge
30 {
31     int u,v;
32     double dis;
33     Edge(){}
34     Edge(int x,int y)
35     {
36         this->u=x;
37         this->v=y;
38         dis=dist(p[x],p[y]);
39     }
40     
41     bool operator<(const Edge& a)const
42     {
43         return dis<a.dis;
44     }
45 }E[maxn*maxn];
46 int parent[maxn];
47 
48 int find(int x)
49 {
50     return x==parent[x]?x:parent[x]=find(parent[x]);
51 }
52 
53 void Kruskal()
54 {
55     for(int i=0;i<pos;i++)
56     {
57         int pa=find(E[i].u);
58         int pb=find(E[i].v);
59         if(pa!=pb)
60         {
61             parent[pa]=pb;
62             result+=E[i].dis;
63         }
64     }
65 }
66 
67 int main()
68 {
69     int t;
70     scanf("%d
",&t);  //cin>>t;也可以
71     while(t--)
72     {
73         result=0;
74         pos=0;
75         scanf("%d",&n);
76         for(int i=0;i<n;i++)
77         {
78             parent[i]=i;
79             p[i].read();
80             for(int j=0;j<i;j++)
81             {
82                 E[pos++]=Edge(i,j);
83             }
84         }
85         sort(E,E+pos);
86         Kruskal();
87         printf("%.2lf
",result);
88         if(t)
89             printf("
");
90     }
91     return 0;
92 }

View Code

uva,10048

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 const int maxn=100;
 7 int start,tar;
 8 int C,S,Q;
 9 int flag;
10 
11 struct Edge{
12     int u,v;
13     int dec;
14     bool operator<(const Edge& a)const
15     {
16         return dec<a.dec;
17     }
18 }E[1010];
19 
20 struct query
21 {
22     int a,b;
23 }q[10010];
24 
25 int parent[maxn];
26 
27 int find(int x)
28 {
29     return x==parent[x] ? x : parent[x]=find(parent[x]);
30 }
31 
32 void Kruskal()
33 {
34     for(int i=0;i<S;i++)
35     {
36         int pa=find(E[i].u);
37         int pb=find(E[i].v);
38         
39         if(pa!=pb)
40             parent[pa]=pb;
41         if(find(start)==find(tar))
42         {
43             flag=1;
44             printf("%d
",E[i].dec);
45             return;
46         }
47     }
48 }
49 
50 int main()
51 {
52     int cas=1;
53     while(scanf("%d%d%d",&C,&S,&Q) && C+S+Q)
54     {
55         for(int i=0;i<S;i++)
56         {
57             scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].dec);
58         }
59         sort(E,E+S);
60         
61         for(int i=0;i<Q;i++)
62         {
63             scanf("%d%d",&q[i].a,&q[i].b);  //不能一边输入一边输出
64 //wa了几次，晕
65         }
66         
67         if(cas!=1)
68             printf("
");  //这个点要注意，要不然就pr
69         printf("Case #%d
",cas++);
70         
71         for(int i=0;i<Q;i++)
72         {
73             flag=0;
74             for(int i=1;i<=C;i++)
75                 parent[i]=i;
76             start=q[i].a;tar=q[i].b;
77             Kruskal();
78             if(!flag)
79                 printf("no path
");
80         }
81     }
82     return 0;
83 }

View Code

uva,10397

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 const int maxn=760;
 8 int N,M;
 9 int pos;
10 double result;
11 
12 struct cable
13 {
14     int a,b;
15 }p[1010];
16 
17 struct Point
18 {
19     int x,y;
20     void read()
21     {
22         scanf("%d%d",&x,&y);
23     }
24 }q[maxn];
25 
26 double dist(Point a,Point b)
27 {
28     int dx=a.x-b.x;
29     int dy=a.y-b.y;
30     return sqrt(dx*dx+dy*dy);
31 }
32 
33 struct Edge
34 {
35     int u,v;
36     double dis;
37     Edge(){}
38     Edge(int x,int y)
39     {
40         this->u=x;
41         this->v=y;
42         dis=dist(q[x],q[y]);
43     }
44     bool operator<(const Edge& a)const
45     {
46         return dis<a.dis;
47     }
48 }E[maxn*maxn];
49 
50 int parent[maxn];
51 int find(int x)
52 {
53     return x==parent[x] ? x:parent[x]=find(parent[x]);
54 }
55 
56 void Kruskal()
57 {
58     for(int i=0;i<pos;i++)
59     {
60         int pa=find(E[i].u);
61         int pb=find(E[i].v);
62         if(pa!=pb)
63         {
64             parent[pa]=pb;
65             result+=E[i].dis;
66         }
67         
68     }
69 }
70 
71 int main()
72 {
73     while(~scanf("%d",&N))
74     {
75         pos=0;
76         for(int i=0;i<N;i++)
77         {
78             parent[i]=i;
79             q[i].read();
80             for(int j=0;j<i;j++)
81                 E[pos++]=Edge(i,j);
82         }
83         
84         scanf("%d",&M);
85         int m,n;
86         for(int i=0;i<M;i++)
87         {
88             scanf("%d%d",&m,&n);
89             int pa=find(m-1);
90             int pb=find(n-1);
91             if(pa!=pb)
92                 parent[pa]=pb; //直接做父亲，然后就就相当于标记了为0
93         }
94         sort(E,E+pos);
95         result=0;
96         Kruskal();
97         printf("%.2lf
",result);
98     }
99 }

View Code

活在现实，做在梦里。