首页 > 代码库 > BZOJ 4349: 最小树形图
BZOJ 4349: 最小树形图
Description
\(n\)个节点，每个节点有一个攻击代价和需要攻击的次数。
有\(k\)个关系，攻击\(x\)后，\(y\)的攻击代价变成\(z\)。
Solution
朱刘算法。
这个好像就是求什么最小树形图的东东...
最小树形图跟最小生成树差不多，不过最小生成树是无向图，最小树形图是有向图，让一个节点和其他节点联通的最小代价。
这个建模也非常容易，只需要确定第一次的攻击即可，之后的一定都以最小代价攻击。
朱刘算法也很简单，步骤就是
找到每个节点的最小入边。
统计答案。
找环，缩环，把边权设成原边权-最小入边边权。
Code
/************************************************************** Problem: 2260 User: BeiYu Language: C++ Result: Accepted Time:8 ms Memory:1340 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; inline int in(int x=0,char ch=getchar()) { while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; } const int N = 55;const int M = N*N+50; struct Edge { int fr,to;double v; };Edge edge[M]; int n,m,rt;int b[N];double mic[N];double miv[N];int pre[N],vis[N],id[N]; void AddEdge(int fr,int to,double v) { edge[++m]=(Edge){ fr,to,v }; } double Solve(int n) { double res=0; for(int cnt,tmp;;) { for(int i=1;i<=n;i++) miv[i]=1e9,pre[i]=0; for(int i=1;i<=m;i++) { Edge &e=edge[i]; if(e.v<miv[e.to]) miv[e.to]=e.v,pre[e.to]=e.fr; } for(int i=1;i<=n;i++) if(pre[i]) res+=miv[i]; memset(vis,0,sizeof(vis)); memset(id,0,sizeof(id)); vis[0]=tmp=1,cnt=0; for(int i=1;i<=n;i++) if(!vis[i]) { ++tmp;int u=i; for(;!vis[u];u=pre[u]) vis[u]=tmp; if(vis[u]==tmp) { ++cnt; for(;!id[u];u=pre[u]) id[u]=cnt; } } if(!cnt) break; for(int i=1;i<=n;i++) if(!id[i]) id[i]=++cnt; int mm=m;m=0; for(int i=1;i<=mm;i++) { Edge &e=edge[i]; if(id[e.fr]!=id[e.to]) AddEdge(id[e.fr],id[e.to],e.v-miv[e.to]); } n=cnt; }return res;} int main() { n=in(),rt=n+1; for(int i=1;i<=n;i++) { double x;scanf("%lf",&x); mic[i]=x; b[i]=in(); if(b[i]) AddEdge(rt,i,x); } for(int k=in();k--;) { int x=in(),y=in(); double z;scanf("%lf",&z); if(b[x] && b[y]) { AddEdge(x,y,z); mic[y]=min(mic[y],z); } } double ans=Solve(n+1);// cout<<ans<<endl;// for(int i=1;i<=n;i++) cout<<mic[i]<<" ";cout<<endl; for(int i=1;i<=n;i++) if(b[i]) ans+=(b[i]-1)*mic[i]; printf("%.2lf\n",ans); return 0;}
BZOJ 4349: 最小树形图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。