本文共 1155 字，大约阅读时间需要 3 分钟。
简单DFS。
#include #include #include #include #include #include #include #include #include #include using namespace std;const int maxn=2000+10;map m1;map m2;int n,k,tot;struct Edge{ int u,v,val;}e[maxn];struct Ans{ string name; int cnt;}ans[maxn];int num;vector g[maxn];int flag[maxn];int Block;int cnt[maxn];void dfs(int x){ num++; flag[x]=Block; for(int i=0;i >a>>b>>e[i].val; if(m1[a]==0) { m1[a]=++tot; m2[tot]=a; } if(m1[b]==0) { m1[b]=++tot; m2[tot]=b; } e[i].u=m1[a]; e[i].v=m1[b]; cnt[e[i].v]+=e[i].val; cnt[e[i].u]+=e[i].val; g[e[i].u].push_back(e[i].v); g[e[i].v].push_back(e[i].u); } num=0; int t=0; for(int i=1;i<=tot;i++) { if(flag[i]!=0) continue; Block++; num=0; dfs(i); if(num<=2) continue; int sum=0; for(int j=1;j<=n;j++) if(flag[e[j].u]==Block&&flag[e[j].v]==Block) sum=sum+e[j].val; if(sum<=k) continue; int id,Max=-1; for(int j=1;j<=tot;j++) if(flag[j]==Block&&cnt[j]>Max) Max=cnt[j],id=j; ans[t].name=m2[id]; ans[t].cnt=num; t++; } sort(ans,ans+t,cmp); printf("%d\n",t); for(int i=0;i
转载于:https://www.cnblogs.com/zufezzt/p/5515740.html