题目大意:给一张无向图,求出最小树形图。
题目分析:套朱-刘算法模板就行了。。。
代码如下:
# 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 (最小树形图、朱刘算法模板)的更多相关文章
-
poj3164(最小树形图&;朱刘算法模板)
题目链接:http://poj.org/problem?id=3164 题意:第一行为n, m,接下来n行为n个点的二维坐标, 再接下来m行每行输入两个数u, v,表点u到点v是单向可达的,求这个有向 ...
-
UVA 11183 Teen Girl Squad 最小树形图
最小树形图模板题 #include <iostream> #include <algorithm> #include <cstdio> #include <c ...
-
最小树形图——朱刘算法(Edmonds)
定义:一个有向图,存在从某个点为根的,可以到达所有点的一个最小生成树,则它就是最小树形图. 朱刘算法实现过程: [在选出入边集后(看步骤1),若有向图中不存在有向环,说明该图就是最小树形图] 1,选入 ...
-
POJ 3164 Command Network ( 最小树形图 朱刘算法)
题目链接 Description After a long lasting war on words, a war on arms finally breaks out between littlek ...
-
POJ 3164 Command Network 最小树形图 朱刘算法
=============== 分割线之下摘自Sasuke_SCUT的blog============= 最 小树形图,就是给有向带权图中指定一个特殊的点root,求一棵以root为根的有向生成树T, ...
-
最小树形图--朱刘算法([JSOI2008]小店购物)
题面 luogu Sol 首先设一个 \(0\) 号点,向所有点连边,表示初始价值 显然这个图的一个 \(0\) 为根的最小有向生成树的边权和就是每个买一次的最小价值 再买就一定能优惠(包含 \(0\ ...
-
洛谷P4716 【模板】最小树形图(朱刘算法)
题意 题目链接 Sol 朱刘算法?感觉又是一种神仙贪心算法 大概就是每次贪心的用每个点边权最小的入边更新答案,如果不行的话就缩起来找其他的边 不详细说了,丢链接走人.. #include<bit ...
-
POJ - 3164-Command Network 最小树形图——朱刘算法
POJ - 3164 题意: 一个有向图,存在从某个点为根的,可以到达所有点的一个最小生成树,则它就是最小树形图. 题目就是求这个最小的树形图. 参考资料:https://blog.csdn.net/ ...
-
bzoj 4349 最小树形图——朱刘算法
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4349. 学习博客:http://www.cnblogs.com/xzxl/p/7243466 ...
随机推荐
-
Senparc.Weixin.MP SDK 微信公众平台开发教程(十一):高级接口说明
这里所说的高级接口是指面向通过认证的服务号开通的高级功能. 高级功能大致可以分类为: 用户接口 分组接口 客服接口(有别于之前介绍的多客服) 群发接口 多媒体接口 二维码接口 模板消息接口(不是所有账 ...
-
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 ...
-
【原创】storyboard启动应用程序的大致流程
storyboard启动应用程序的大致流程 [原创] 转载请注明出处:http://i.cnblogs.com/EditPosts.aspx?postid=5395023 1. 用户点击APP图标—— ...
-
洛谷 [P1402] 酒店之王
有两个约束条件的二分图匹配 我们回忆一下二分图匹配的匈牙利算法的具体流程,它是通过寻找增广路来判断最大匹配数的,我们再观察一下题目中的两个条件,只有两个条件都满足,才算找到一条增广路,所以我们可以分别 ...
-
bzoj千题计划219:bzoj1568: [JSOI2008]Blue Mary开公司
http://www.lydsy.com/JudgeOnline/problem.php?id=1568 写多了就觉着水了... #include<cstdio> #include< ...
-
微信小程序wepy开发循环wx:for需要注意
微信小程序wepy开发循环wx:for需要注意 item index值必须在wx:for之后使用 <view wx:for="{{tablist}}" class=" ...
-
Nearest neighbor graph | 近邻图
最近在开发一套自己的单细胞分析方法,所以copy paste事业有所停顿. 实例: R eNetIt v0.1-1 data(ralu.site) # Saturated spatial graph ...
-
org.apache.ibatis.builder.IncompleteElementException: Could not find result map java.util.HashMap
这样的配置有问题吗? <select id="getFreightCollectManagementList" resultMap="java.util.HashM ...
-
跳表,Redis 为什么用跳表而不用平衡树?
https://juejin.im/post/57fa935b0e3dd90057c50fbc 在 Redis 中,list 有两种存储方式:双链表(LinkedList)和压缩双链表(ziplist ...
-
[Node.js] 06 - Multi-thread and process module
课前阅读:关于Node.js后端架构的一点后知后觉 书推荐:<Node.js design patterns> 衍生问题: 微服务的必要性,Flux架构 容错性和拓展性 一.立体拓展 假设 ...