codeforces 1245DShichikuji and Power Grid

题意：：求让所有城市连接起来的最小花费连接方式（1：在城市建立发电站 2：用电线连接有发电站的城市）

思路：：最小生成树，倘若在城市建电站，花费 c[ i ] ,反之连接其他城市花费 k[i]+k[j])*(i,j曼哈顿距离)

我们可以建立一个虚点，他到所有城市的花费即为自建花费

然后跑最小生成树，不仅保证图联通，还是最小花费，需要注意一下自建电站情况

Kruskal

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 const ll inf=1e15+7;
 4 using namespace std;
 5 const int maxn=2005;
 6 
 7 struct node
 8 {
 9     int x,y;
10     ll x1,y1,val;
11     bool operator < (const node &lh)const {return val<lh.val;}
12 }ma[maxn],mb[maxn*maxn+2500];
13 int n,t=0,f[maxn],a[maxn];
14 ll sum=0,c[maxn],k[maxn];
15 vector<pair<int,int> >v;
16 
17 ll dis(int x,int y)
18 {
19     ll num=(abs(ma[x].x1-ma[y].x1)+abs(ma[x].y1-ma[y].y1))*(k[x]+k[y]);
20     return num;
21 }
22 int getfind(int x)
23 {
24     return x==f[x]?x:f[x]=getfind(f[x]);
25 }
26 void init()
27 {
28     for(int i=0;i<=n;i++)f[i]=i;
29 }
30 int main()
31 {
32     v.clear();
33     scanf("%d",&n);
34     for(int i=1;i<=n;i++){
35         scanf("%lld%lld",&ma[i].x1,&ma[i].y1);
36     }
37     for(int i=1;i<=n;i++){
38         scanf("%lld",&c[i]);
39     }
40     for(int i=1;i<=n;i++){
41         scanf("%lld",&k[i]);
42     }
43     int ant=0;
44     for(int i=1;i<=n;i++){
45         for(int j=i+1;j<=n;j++){
46             mb[++ant].x=i;mb[ant].y=j;mb[ant].val=dis(i,j);
47         }
48     }
49     n++;init();
50     for(int i=1;i<n;i++){
51         mb[++ant].x=i;mb[ant].y=n;mb[ant].val=c[i];
52     }
53     sort(mb+1,mb+ant+1);
54     for(int i=1;i<=ant;i++){
55         int k1=mb[i].x,k2=mb[i].y;
56         int t1=getfind(k1),t2=getfind(k2);
57         if(t1!=t2){
58             f[t1]=t2;
59             sum+=mb[i].val;
60             if(k2==n){a[++t]=k1;}
61             else{
62                 v.push_back(make_pair(k2,k1));
63             }
64         }
65     }
66     printf("%lld
%d
",sum,t);
67     for(int i=1;i<=t;i++){
68         printf("%d ",a[i]);
69     }
70     printf("
%d
",v.size());
71     for(int i=0;i<v.size();i++){
72         printf("%d %d
",v[i].first,v[i].second);
73     }
74     return 0;
75 }

View Code

Prime

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 const ll inf=1e15+7;
 4 using namespace std;
 5 const int maxn=2005;
 6  
 7 struct node
 8 {
 9     ll x,y;
10 }ma[maxn],mb[maxn];
11 int n,t=0;
12 ll sum=0;
13 ll c[maxn],a[maxn];
14 ll k[maxn],lowdis[maxn];
15 ll mst[maxn];
16  
17 vector<pair<ll,ll> >v;
18  
19 ll dis(int x,int y)
20 {
21     ll num=(abs(ma[x].x-ma[y].x)+abs(ma[x].y-ma[y].y))*(k[x]+k[y]);
22     return num;
23 }
24  
25 void prime()
26 {
27     for(int i=1;i<=n;i++){
28         lowdis[i]=c[i];
29     }
30     for(int i=1;i<=n;i++)
31     {
32         ll minn=inf;
33         ll mind=0;
34         for(int j=1;j<=n;j++)
35         {
36             if(minn>lowdis[j]&&lowdis[j]!=0){
37                 minn=lowdis[j];
38                 mind=j;
39             }
40         }
41         lowdis[mind]=0;
42         sum+=minn;
43         if(!mst[mind]){
44             a[++t]=mind;
45  
46         }
47         else{
48             v.push_back(make_pair(mst[mind],mind));
49         }
50         for(int j=1;j<=n;j++){
51             if(lowdis[j]>dis(mind,j)){
52                 lowdis[j]=dis(mind,j);mst[j]=mind;
53             }
54         }
55     }
56     printf("%lld
%d
",sum,t);
57 }
58 int main()
59 {
60     scanf("%d",&n);
61     for(int i=1;i<=n;i++){
62         scanf("%lld%lld",&ma[i].x,&ma[i].y);
63     }
64     for(int i=1;i<=n;i++){
65         scanf("%lld",&c[i]);
66     }
67     for(int i=1;i<=n;i++){
68         scanf("%lld",&k[i]);
69     }
70     prime();
71     for(int i=1;i<=t;i++){
72         printf("%lld ",a[i]);
73     }
74     printf("
%d
",v.size());
75     for(int i=0;i<v.size();i++){
76         printf("%lld %lld
",v[i].first,v[i].second);
77     }
78     return 0;
79 }

View Code

码风有点怪，还能看

纵使单枪匹马，也要勇闯天涯