-
Notifications
You must be signed in to change notification settings - Fork 2
/
Prims_MST
141 lines (115 loc) · 2.87 KB
/
Prims_MST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/// used to solve https://codeforces.com/problemset/problem/1245/D
/// can find minimum spanning tree in O(n*n)
/// will traverse all n*n edges and not required any log(n) factor to find minimum cost edge.
/// initially all nodes make edge with node 0, that 0 is the root
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
#define MP make_pair
#define PB push_back
#define pb push_back
#define nn '\n'
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define UNIQUE(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end()))) ;
#define all(vec) vec.begin(),vec.end()
#define int long long
#define pii pair<int,int>
#define pdd pair<double,double>
#define ff first
#define ss second
#define edge(u,v) adj[u].pb(v) , adj[v].pb(u)
#define white 0
#define blue 1
#define red 2
using namespace std ;
typedef long long LL ;
const int MOD=1e9+7 ;
const int N=2e6+7 ;
const int oo=2LL*MOD*MOD*1LL+MOD ;
const double pie=acos(-1.0) ;
const double EPS=1e-9 ;
int n, x[2003], y[2003], c[2003], k[2003], p[2003];
int Manhattan_Distance(int i, int j)
{
return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}
int Cost(int u, int v)
{
return Manhattan_Distance(u, v)*(k[u] + k[v]);
}
void Prims_Spanning_Tree(int &sm, vector<int> &tower, vector<pii> &e)
{
vector<int>dp(n+5, oo), pa(n+5, 0), used(n+5, 0);
for(int i=1; i<=n; i++)
{
dp[i] = c[i];
}
for(int it=1; it<=n; ++it)
{
int v = n+1;
for(int u=1; u<=n; ++u)
{
if(!used[u] and dp[u]<dp[v])
{
v = u;
}
}
used[v] = 1;
sm += dp[v];
if(pa[v]==0)
{
tower.push_back(v);
}
else
{
e.push_back({pa[v], v});
}
/// update ...
for(int u=1; u<=n; ++u)
{
if(!used[u] and Cost(u, v)<dp[u])
{
dp[u] = Cost(u, v);
pa[u] = v;
}
}
}
}
int32_t main()
{
IOS
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>x[i]>>y[i];
}
vector<pii>vec;
for(int i=1; i<=n; i++)
{
cin>>c[i];
vec.pb({c[i], i});
}
for(int i=1; i<=n; i++)
{
cin>>k[i];
}
int sm = 0;
vector<pii>e;
vector<int>tower;
Prims_Spanning_Tree(sm, tower, e);
cout<<sm<<endl;
cout<<n - e.size()<<endl;
for(int t:tower)
{
cout<<t<<' ';
}
cout<<endl<<e.size()<<endl;
for(pii p:e)
{
cout<<p.ff<<' '<<p.ss<<endl;
}
return 0;
}