Pagini recente » Cod sursa (job #2711368) | Cod sursa (job #1798610) | Cod sursa (job #2422384) | Cod sursa (job #2696412) | Cod sursa (job #1705218)
# include <fstream>
# include <climits>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int maxn = 10000;
int mc[maxn][maxn],n,m,cost;
void prim(int radacina)
{
int rad, i, j, min, s[maxn], t[maxn], K;
rad = radacina;
for (i = 1; i <= n; i++)
s[i] = rad;
s[rad] = 0;
for (i = 1; i <= n; i++)
t[i] = 0;
cost = 0;
for (K = 1; K <= n - 1; K++)
{
min = INT_MAX;
for (i = 1; i <= n; i++)
if (s[i])
if (mc[s[i]][i] < min && mc[s[i]][i])
{
min = mc[s[i]][i];
j = i;
}
t[j] = s[j];
cost =cost + min;
s[j] = 0;
for (i = 1; i <= n; i++)
if (s[i])
if (!mc[i][s[i]] || mc[i][s[i]]>mc[i][j])
if (mc[i][j])
s[i] = j;
}
g << cost << "\n";
g << K << "\n";
for (i = 1; i <= n; i++)
if (t[i] != 0)
g << i << " " << t[i] << "\n";
}
int main()
{
f >> n >> m;
int i, j, x, y, z;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
mc[i][j] = INT_MAX;
for (i = 1; i <= m; i++)
{
f >> x >> y >> z;
mc[x][y] = mc[y][x] = z;
}
prim(1);
}