某个局域网内有n(n<=100)台计算机,由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据将不停的在回路内传输,造成网络卡的现象。因为连接计算机的网线本身不同,所以有一些连线不是很畅通,我们用f(i,j)表示i,j之间连接的畅通程度,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)的最大值
输入输出样例
输入样例#1: 复制
5 5 1 2 8 1 3 1 1 5 3 2 4 5 3 4 2
输出样例#1: 复制
8
最小生成树模板题:只要总的权值减最小生成树即可
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define LL long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define N 1000 int n,m; int ans; int mp[N][N]; int vis[N]; struct edge { int to;//to为通向的边 int v;//为权值 friend bool operator<(const edge& a,const edge& b) { return a.v>b.v; } }now; void prim(int s) { vis[s]=1; priority_queue<edge>q; while(!q.empty())q.pop(); rep(i,1,n) { rep(j,1,n) if(!vis[j]) { now.to=j; now.v=mp[s][j]; q.push(now); } while(!q.empty()&&vis[q.top().to]) q.pop(); if(q.empty())break; now=q.top();q.pop(); s=now.to; ans+=now.v; vis[s]=1; } } int main() { CLR(vis,0); RII(n,m); rep(i,1,n) rep(j,1,n) mp[i][j]=inf; int sum=0; while(m--) { int a,b,c; RIII(a,b,c); sum+=c; mp[a][b]=mp[b][a]=c; } prim(1); cout<<sum-ans<<endl; return 0; }
#define inf 0x3f3f3f3f #define N 1000 int n,m,f[200],ans,x; struct lol{ int from,to,val;//使用结构体存储边的两端点,长度 }l[20010]; bool cmp(lol a, lol b){ return a.val<b.val;//sort排序设置边长为关键字 } int find1(int x){ if (f[x]==x) return x; else return f[x]=find(f[x]);//并查集 } int kuskal(){ int a,b; int ans=0; x=0; sort(l+1,l+1+m,cmp);//sort快排 for (int i=1; i<=m; i++){ a=find1(l[i].from); b=find1(l[i].to);//找两点的祖先 if (a==b) continue;//ab在同一集合,即a,b点已连通,则跳过 ans+=l[i].val;//记录长度 f[a]=b;//合并 x++; if (x==n) return ans;//边达到需要值,跳出函数 } return ans; } int main(){ int i; cin>>n>>m; for (i=1; i<=n; i++){ f[i]=i; } for (i=1; i<=m; i++){ scanf("%d%d%d",&l[i].from,&l[i].to,&l[i].val); ans+=l[i].val;//算总长 } printf("%d",ans-kuskal());//输出 return 0; }