14 图论

#include
using namespace std;
#include
#include
int const N = 510;
int a, n;
int g[N][N];
bool vis[N];
int fat[N];
struct things
{
	int x;
	int y;
	int money;
};
vectorv;
bool compare(things t1, things t2)
{
	return t1.money < t2.money;
}
int father(int x)
{
	return fat[x] == x ? x : father(fat[x]);
}
int main()
{
	cin >> a >>n;
	for (int i = 1;i <= n;i++)	
	{
		fat[i] = i;
		for (int j = 1;j <= n;j++)
		{
			cin >> g[i][j];
			if (g[i][j] == 0)
			{
				g[i][j] = a;
			}
		}
	}
	things t;
	for (int i = 1;i < n;i++)
	{
		for (int j = i + 1;j <= n;j++)
		{
			t.x = i;
			t.y = j;
			t.money = g[i][j];
			v.push_back(t);
		}
	}
	sort(v.begin(), v.end(), compare);
	int cnt = 1;
	long long ans = a;
	for (vector::iterator it = v.begin();it != v.end();it++)
	{
		if (father((*it).x) != father((*it).y))
		{
			int x = father((*it).x), y = father((*it).y);
			fat[x] = fat[y];
			cnt++;
			if ((*it).money < a)
			{
				ans += (*it).money;
			}
			else
			{
				ans += a;
			}
		}
		if (cnt == n)break;
	}
	cout << ans << endl;
	return 0;
}

 

#include
#include
using namespace std;
int const N = 1010;
int fa[N];
int find(int x)
{
	if (fa[x] != x)
	{
		fa[x] = find(fa[x]);
	}
	return fa[x];
}
void unity(int x, int y)
{
	int r1 = find(x);
	int r2 = find(y);
	fa[r1] = r2;
}
int main()
{
	int n, k;
	cin >> n;
	while (n != 0)
	{
		cin >> k;
		for (int i = 1;i <= n;i++)
		{
			fa[i] = i;
		}
		for (int i = 1;i <= k;i++)
		{
			int u, v;
			cin >> u >> v;
			unity(u, v);
		}
		int ans = -1;
		for (int i = 1;i <= n;i++)
		{
			if (fa[i] == i)
			{
				ans++;
			}
		}
		cout << ans << endl;
		cin >> n;
	}
	return 0;
}

 

#include
using namespace std;
#include
#include
int n, m, k;
int fa[1010];
int find(int x)
{
	if (fa[x] != x)
	{
		fa[x] = find(fa[x]);
	}
	return fa[x];
}
void unity(int x, int y)
{
	int r1 = find(x);
	int r2 = find(y);
	fa[r1] = r2;
}
struct lt
{
	int x;
	int y;
	int dj;
};
bool cmp(lt l1, lt l2)
{
	return l1.dj < l2.dj;
}
int main()
{
	vectorv;
	lt l;
	cin >> n >> m >> k;
	for (int i = 1;i <= n;i++)
	{
		fa[i] = i;
	}
	for (int i = 1;i <= m;i++)
	{
		cin >> l.x >> l.y >> l.dj;
		v.push_back(l);
	}
	sort(v.begin(), v.end(), cmp);
	int cnt = n;
	long long ans = 0;
	int length = v.size();	
	//cout << endl << endl << endl;
	for (int i = 0;i < length;i++)
	{
		//cout << v[i].x<<" " << v[i].y<<" " << v[i].dj << endl;
		if (cnt == k)
		{
			cout << ans << endl;
			return 0;
		}
		if (find(v[i].x) != find(v[i].y))
		{
			unity(find(v[i].x), find(v[i].y));
			ans += v[i].dj;
			cnt--;
		}
		if (cnt == k)
		{
			cout << ans << endl;
			return 0;
		}
	}
	cout << "No Answer" << endl;	
	return 0;
}

 

 

 

#include
using namespace std;
#include
#include
int n, m, s, t;
int const N = 101000;
int fa[N];
struct lu
{
	int x;
	int y;
	int yongji;
};
bool cmp(lu l1, lu l2)
{
	return l1.yongji < l2.yongji;
}
int find(int x)
{
	if (fa[x] != x)
	{
		fa[x] = find(fa[x]);
	}
	return fa[x];
}
void unity(int x, int y)
{
	int r1 = find(x);
	int r2 = find(y);
	fa[r1] = r2;
}
int main()
{
	cin >> n >> m >> s >> t;
	vectorv;
	lu l;
	for (int i = 1;i <= n;i++)
	{
		fa[i] = i;
	}
	for (int i = 1;i <= m;i++)
	{
		cin >> l.x >> l.y >> l.yongji;
		v.push_back(l);
	}
	sort(v.begin(), v.end(), cmp);
	long long ans = 0;
	for (vector::iterator it = v.begin();it != v.end();it++)
	{
		int x = (*it).x;
		int y = (*it).y;
		if (find(x) != find(y))
		{
			unity(find(x), find(y));
		}
		if (find(s) == find(t))
		{
			cout <<(*it).yongji << endl;
			return 0;
		}
	}
	return 0;
}

#include
#include
using namespace std;
int const N = 110;
struct wl
{
	int x;
	int y;
	int jl;
};
int n;
int fa[N];
int g[N][N];
wl w[N*N];
bool cmp(wl w1, wl w2)
{
	return w1.jl < w2.jl;
}
int find(int x)
{
	if (fa[x] != x)
	{
		fa[x] = find(fa[x]);
	}
	return fa[x];
}
void unity(int x, int y)
{
	int r1 = find(x);
	int r2 = find(y);
	fa[r1] = r2;
}
int main()
{
	cin >> n;
	for (int i = 1;i <= n;i++)
	{
		fa[i] = i;
		for (int j = 1;j <= n;j++)
		{
			cin >> g[i][j];
		}
	}
	int flag = 1;
	for (int i = 1;i < n;i++)
	{
		for (int j = i + 1;j <= n;j++)
		{
			w[flag].x = i;
			w[flag].y = j;
			w[flag].jl = g[i][j];
			flag++;
		}
	}
	sort(w + 1, w + flag, cmp);
	long long ans = 0;
	int cnt = 1;
	for (int i = 1;i <= flag;i++)
	{
		int x = find(w[i].x);
		int y = find(w[i].y);
		if (x != y)
		{
			cnt++;
			ans += w[i].jl;
			unity(x, y);
		}
		if (cnt == n)
		{
			cout << ans << endl;
			return 0;
		}
	}
	return 0;
}

 

#include
#include
#include
#include
#include
using namespace std;
int n, m, s;
int const N = 100010;
int dis[N];
bool vis[N];
struct edge
{
	int u;
	int v;
	int w;
};
struct node
{
	int number;
	int dis;
	bool operator < (const node& x)const { return x.dis < dis; }
};
vectorvt[N];
priority_queueq;
void dijkstra()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	q.push({ s,0 });
	while (!q.empty())
	{
		int x = q.top().number;
		q.pop();
		if (vis[x])continue;
		vis[x] = true;
		for (vector::iterator it = vt[x].begin();it != vt[x].end();it++)
		{
			int p = (*it).v;
			if (vis[p])continue;
			if (dis[p] > dis[x] + (*it).w)
			{
				dis[p] = dis[x] + (*it).w;
				q.push({ p,dis[x] + (*it).w });
			}
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	edge e;
	for (int i = 1;i <= m;i++)
	{
		cin >> e.u >> e.v >> e.w;
		vt[e.u].push_back(e);
	}
	dijkstra();
 
	for (int i = 1;i <= n;i++)
	{
		cout << dis[i] << " ";
	}
	return 0;
}