- 1 2 2 3 3 4 3 5
- #include<bits/stdc++.h>
- using namespace std;
- const int maxM = 10005, maxN = 105;
- struct edge{
- int u,v,w;
- };
- int f[maxN];
- edge G[maxM];
- struct node{
- int u,v;
- bool operator <(const node A)const{
- if(A.u == u)return A.v < v;
- return A.u < u;
- }
- };
- priority_queue <node>Q;
- int Find(int x){
- if(f[x]==x)return x;
- else return f[x]=Find(f[x]);
- }
- bool Same(int x,int y){
- return Find(x)==Find(y);
- }
- void Unionset(int x,int y){
- int u=Find(x),v=Find(y);
- if(u==v)return;
- else f[u]=v;
- }
- bool cmp(edge x,edge y){
- return x.w<y.w;
- }
- int main(){
- int n,k,tot=0,t=0,ans=0;
- cin>>n>>k;
- for(int i=1;i<=k;i++)
- scanf("%d%d%d",&G[i].u,&G[i].v,&G[i].w);
- for(int i=1;i<=n;i++)f[i]=i;
- sort(G+1,G+1+k,cmp);
- for(int i=1;i<=k;i++){
- if(t==n-1)break;
- if(!Same(G[i].u,G[i].v)){
- Unionset(G[i].u,G[i].v);
- Q.push((node){min(G[i].u,G[i].v),max(G[i].u,G[i].v)});
- t++;
- }
- }
- while(!Q.empty()){
- node p = Q.top();
- Q.pop();
- cout<<p.u<<" "<<p.v<<endl;
- }
- }
例 4-10 最优布线问题
时间限制: 1000 ms 内存限制: 65536 KB
题目描述
学校有 n 台计算机, 为了方便数据传输, 现要将它们用数据线连接起来两台计算机被连接是指它们有数据线连接由于计算机所处的位置不同, 因此不同的两台计算机的连接费用往往是不同的
当然, 如果将任意两台计算机都用数据线连接, 费用将是相当庞大的为了节省费用, 我们采用数据的间接传输手段, 即一台计算机可以间接的通过若干台计算机 (作为中转) 来实现与另一台计算机的连接
现在由你负责连接这些计算机, 任务是使任意两台计算机都连通(不管是直接的或间接的)
输入
第一行为整数 n(2n100), 表示计算机的数目此后的 n 行, 每行 n 个整数第 x+1 行 y 列的整数表示直接连接第 x 台计算机和第 y 台计算机的费用
输出
一个整数, 表示最小的连接费用
输入样例
3 0 1 2 1 0 1 2 1 0
输出样例
2
提示
注: 表示连接 1 和 2,2 和 3, 费用为 2
- #include<bits/stdc++.h>
- using namespace std;
- #define maxn 105
- #define INF 10000008
- struct edge{
- int to,co;
- };
- vector <edge> G[maxn];
- int minx[maxn];
- bool vis[maxn];
- int main(){
- int N, MST = 0;
- cin>>N;
- for(int i = 1; i <= N; i++)
- for(int j = 1; j <= N; j++){
- int w;
- cin>>w;
- if(w)G[i].push_back((edge){j,w});
- }
- memset(minx,0x7f,sizeof(minx));
- minx[1] = 0;
- for(int i = 1; i <= N; i++){
- int minn = INF, k = 0;
- for(int j = 1; j <= N; j++){
- if(minx[j] < minn && !vis[j])
- minn = minx[j], k = j;
- }
- vis[k] = 1;
- MST += minx[k];
- for(int m = 0; m < G[k].size(); m++){
- edge v = G[k][m];
- if(!vis[v.to] && minx[v.to] > v.co)
- minx[v.to] = v.co;
- }
- }
- cout<<MST<<endl;
- }
局域网(net)
时间限制: 1000 ms 内存限制: 65536 KB
题目描述
某个局域网内有 n(n100)台计算机, 由于搭建局域网时工作人员的疏忽, 现在局域网内的连接形成了回路, 我们知道如果局域网形成回路那么数据将不停的在回路内传输, 造成网络卡的现象因为连接计算机的网线本身不同, 所以有一些连线不是很畅通, 我们用 f(i,j)表示 i,j 之间连接的畅通程度 (f(i,j)1000),f(i,j) 值越小表示 i,j 之间连接越通畅, f(i,j)为 0 表示 i,j 之间无网线连接现在我们需要解决回路问题, 我们将除去一些连线, 使得网络中没有回路, 并且被除去网线的Σf(i,j)最大, 请求出这个最大值
输入
第一行两个正整数 n k
接下来的 k 行每行三个正整数 i j m 表示 i,j 两台计算机之间有网线联通, 通畅程度为 m
输出
一个正整数,Σf(i,j)的最大值
输入样例
- 5 5
- 1 2 8
- 1 3 1
- 1 5 3
- 2 4 5
- 3 4 2
输出样例
- 8
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 105;
- struct edge{
- int u,v,w;
- };
- int f[maxn];
- edge G[maxn*maxn];
- int Find(int x){
- if(f[x]==x)return x;
- else return f[x]=Find(f[x]);
- }
- bool Same(int x,int y){
- return Find(x)==Find(y);
- }
- void Unionset(int x,int y){
- int u=Find(x),v=Find(y);
- if(u==v)return;
- else f[u]=v;
- }
- bool cmp(edge x,edge y){
- return x.w<y.w;
- }
- int main(){
- int n,k,tot=0,t=0,ans=0;
- cin>>n>>k;
- for(int i=1;i<=k;i++){
- scanf("%d%d%d",&G[i].u,&G[i].v,&G[i].w);
- tot+=G[i].w;
- }
- for(int i=1;i<=n;i++)f[i]=i;
- sort(G+1,G+1+k,cmp);
- for(int i=1;i<=k;i++){
- if(t==n-1)break;
- if(!Same(G[i].u,G[i].v)){
- Unionset(G[i].u,G[i].v);
- ans+=G[i].w;
- t++;
- }
- }
- cout<<tot-ans<<endl;
- }
来源: http://www.bubuko.com/infodetail-2507102.html