首页 > 编程学习 > HDU-6041 I Curse Myself(双连通分量+k路归并)

HDU-6041 I Curse Myself(双连通分量+k路归并)

发布时间:2022/12/10 17:05:24

传送门:HDU-6041

题解:这个图是仙人掌,因此要形成生成树,每个环都得去掉一条边,因此可以将每个环上的边权值看成一个集合,要求每一个集合中选一个数加起来,求所有和中前k大的为多少,这样就能转换成k路归并

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MX = 1e3 + 5;
const int MXE = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct Edge{int v,w,nxt;
}E[MX*4];
int head[MX],rear,n,m,k;
int arr[MXE],ans[MXE],tmp[MXE];
int dfn[MX],tot;
stack<int>st;
void init(){for(int i=1;i<=n;i++) head[i]=-1,dfn[i]=0;rear=tot=0;ans[0]=0;ans[++ans[0]]=0;
}
void add(int u,int v,int w){E[rear].v=v;E[rear].w=w;E[rear].nxt=head[u];head[u]=rear++;
}
struct node{int val,u,v;node(){}node(int val,int u,int v):val(val),u(u),v(v){}bool operator<(const node& _A)const{return val<_A.val;}
};
void merge(int *A,int *B){priority_queue<node>q;sort(B+1,B+B[0]+1);for(int i=1;i<=B[0];i++) q.push(node(A[1]+B[i],1,i));tmp[0]=0;while(tmp[0]<k&&!q.empty()){node p=q.top();q.pop();tmp[++tmp[0]]=p.val;if(p.u<A[0]) q.push(node(A[p.u+1]+B[p.v],p.u+1,p.v));}for(int i=0;i<=tmp[0];i++) A[i]=tmp[i];
}int dfs(int u,int fa){int lowu=dfn[u]=++tot;int son=0;for(int i=head[u];~i;i=E[i].nxt){int v=E[i].v;if(!dfn[v]){ //没被访问过st.push(i);son++;int lowv=dfs(v,u);lowu=min(lowu,lowv);if(lowv>=dfn[u]){  //v没有连向u祖先的边arr[0]=0;for(;;){int id=st.top();st.pop();arr[++arr[0]]=E[id].w;if(id==i) break;}if(arr[0]>1) merge(ans,arr);}}else if(dfn[v]<dfn[u]&&v!=fa){st.push(i);lowu=min(lowu,dfn[v]);}}return lowu;
}
void find_bcc(int n){for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,-1);
}int main() {//freopen("in.txt","r",stdin);int cas=0;while(~scanf("%d%d",&n,&m)){init();int sum=0;for(int i=1,u,v,w;i<=m;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);sum+=w;}scanf("%d",&k);find_bcc(n);unsigned ret=0;for(int i=1;i<=ans[0];i++)ret+=(unsigned)(sum-ans[i])*i;printf("Case #%d: %u\n",++cas,ret);}return 0;
}



本文链接:https://www.ngui.cc/el/2314421.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000