UVA-11183 Teen Girl Squad (最小树形图、朱刘算法模板)

时间:2020-12-22 13:24:23

题目大意:给一张无向图,求出最小树形图。

题目分析:套朱-刘算法模板就行了。。。

代码如下:

# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;
# define LL long long
# define REP(i,s,n) for(int i=s;i<n;++i)
# define CL(a,b) memset(a,b,sizeof(a))
# define CLL(a,b,n) fill(a,a+n,b) const int N=1005;
const int INF=1<<30;
struct Edge
{
int fr,to,w;
};
Edge e[N*40];
int vis[N],ID[N],pre[N],in[N],n,m; int zhu_liu(int root,int nv,int ne)
{
int res=0;
while(1)
{
CLL(in,INF,nv);
REP(i,0,ne) if(e[i].fr!=e[i].to&&in[e[i].to]>e[i].w){
in[e[i].to]=e[i].w;
pre[e[i].to]=e[i].fr;
}
in[root]=0;
REP(i,0,nv) if(in[i]==INF) return -1;
int nodeCnt=0;
CL(ID,-1);
CL(vis,-1);
REP(i,0,nv){
res+=in[i];
int v=i;
while(vis[v]!=i&&ID[v]==-1&&v!=root){
vis[v]=i;
v=pre[v];
}
if(v!=root&&ID[v]==-1){
for(int u=pre[v];u!=v;u=pre[u])
ID[u]=nodeCnt;
ID[v]=nodeCnt++;
}
}
if(nodeCnt==0) break;
REP(i,0,nv) if(ID[i]==-1) ID[i]=nodeCnt++;
REP(i,0,ne){
int v=e[i].to;
e[i].fr=ID[e[i].fr];
e[i].to=ID[e[i].to];
if(e[i].fr!=e[i].to)
e[i].w-=in[v];
}
nv=nodeCnt;
root=ID[root];
}
return res;
} int main()
{
int T,cas=0;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
REP(i,0,m)
{
scanf("%d%d%d",&e[i].fr,&e[i].to,&e[i].w);
}
int ans=zhu_liu(0,n,m);
printf("Case #%d: ",++cas);
if(ans<0)
printf("Possums!\n");
else
printf("%d\n",ans);
}
return 0;
}

  

UVA-11183 Teen Girl Squad (最小树形图、朱刘算法模板)的更多相关文章

  1. poj3164&lpar;最小树形图&amp&semi;朱刘算法模板&rpar;

    题目链接:http://poj.org/problem?id=3164 题意:第一行为n, m,接下来n行为n个点的二维坐标, 再接下来m行每行输入两个数u, v,表点u到点v是单向可达的,求这个有向 ...

  2. UVA 11183 Teen Girl Squad 最小树形图

    最小树形图模板题 #include <iostream> #include <algorithm> #include <cstdio> #include <c ...

  3. 最小树形图——朱刘算法&lpar;Edmonds&rpar;

    定义:一个有向图,存在从某个点为根的,可以到达所有点的一个最小生成树,则它就是最小树形图. 朱刘算法实现过程: [在选出入边集后(看步骤1),若有向图中不存在有向环,说明该图就是最小树形图] 1,选入 ...

  4. POJ 3164 Command Network ( 最小树形图 朱刘算法)

    题目链接 Description After a long lasting war on words, a war on arms finally breaks out between littlek ...

  5. POJ 3164 Command Network 最小树形图 朱刘算法

    =============== 分割线之下摘自Sasuke_SCUT的blog============= 最 小树形图,就是给有向带权图中指定一个特殊的点root,求一棵以root为根的有向生成树T, ...

  6. 最小树形图--朱刘算法&lpar;&lbrack;JSOI2008&rsqb;小店购物&rpar;

    题面 luogu Sol 首先设一个 \(0\) 号点,向所有点连边,表示初始价值 显然这个图的一个 \(0\) 为根的最小有向生成树的边权和就是每个买一次的最小价值 再买就一定能优惠(包含 \(0\ ...

  7. 洛谷P4716 【模板】最小树形图&lpar;朱刘算法&rpar;

    题意 题目链接 Sol 朱刘算法?感觉又是一种神仙贪心算法 大概就是每次贪心的用每个点边权最小的入边更新答案,如果不行的话就缩起来找其他的边 不详细说了,丢链接走人.. #include<bit ...

  8. POJ - 3164-Command Network 最小树形图——朱刘算法

    POJ - 3164 题意: 一个有向图,存在从某个点为根的,可以到达所有点的一个最小生成树,则它就是最小树形图. 题目就是求这个最小的树形图. 参考资料:https://blog.csdn.net/ ...

  9. bzoj 4349 最小树形图——朱刘算法

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4349. 学习博客:http://www.cnblogs.com/xzxl/p/7243466 ...

随机推荐

  1. Senparc&period;Weixin&period;MP SDK 微信公众平台开发教程(十一):高级接口说明

    这里所说的高级接口是指面向通过认证的服务号开通的高级功能. 高级功能大致可以分类为: 用户接口 分组接口 客服接口(有别于之前介绍的多客服) 群发接口 多媒体接口 二维码接口 模板消息接口(不是所有账 ...

  2. hdu-acm steps Max sum

    /*求最大字段和,d[i]表示已 i 结尾(字段和中包含 i )在 a[1..i] 上的最大和,d[i]=(d[i-1]+a[i]>a[i])?d[i-1]+a[i]:a[i];max = {d ...

  3. 【原创】storyboard启动应用程序的大致流程

    storyboard启动应用程序的大致流程 [原创] 转载请注明出处:http://i.cnblogs.com/EditPosts.aspx?postid=5395023 1. 用户点击APP图标—— ...

  4. 洛谷 &lbrack;P1402&rsqb; 酒店之王

    有两个约束条件的二分图匹配 我们回忆一下二分图匹配的匈牙利算法的具体流程,它是通过寻找增广路来判断最大匹配数的,我们再观察一下题目中的两个条件,只有两个条件都满足,才算找到一条增广路,所以我们可以分别 ...

  5. bzoj千题计划219:bzoj1568&colon; &lbrack;JSOI2008&rsqb;Blue Mary开公司

    http://www.lydsy.com/JudgeOnline/problem.php?id=1568 写多了就觉着水了... #include<cstdio> #include< ...

  6. 微信小程序wepy开发循环wx&colon;for需要注意

    微信小程序wepy开发循环wx:for需要注意 item index值必须在wx:for之后使用 <view wx:for="{{tablist}}" class=&quot ...

  7. Nearest neighbor graph &vert; 近邻图

    最近在开发一套自己的单细胞分析方法,所以copy paste事业有所停顿. 实例: R eNetIt v0.1-1 data(ralu.site) # Saturated spatial graph ...

  8. org&period;apache&period;ibatis&period;builder&period;IncompleteElementException&colon; Could not find result map java&period;util&period;HashMap

    这样的配置有问题吗? <select id="getFreightCollectManagementList" resultMap="java.util.HashM ...

  9. 跳表,Redis 为什么用跳表而不用平衡树?

    https://juejin.im/post/57fa935b0e3dd90057c50fbc 在 Redis 中,list 有两种存储方式:双链表(LinkedList)和压缩双链表(ziplist ...

  10. &lbrack;Node&period;js&rsqb; 06 - Multi-thread and process module

    课前阅读:关于Node.js后端架构的一点后知后觉 书推荐:<Node.js design patterns> 衍生问题: 微服务的必要性,Flux架构 容错性和拓展性 一.立体拓展 假设 ...