最小树形图(tju 2248 UVA 11183 poj 3164)

2024-06-15 19:18

本文主要是介绍最小树形图(tju 2248 UVA 11183 poj 3164),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

求最小树形图的总权值  

即以固定跟为起点 延给定有向边 可以访问所有的点 并所构成的边权值之和最小 求出这个最小总权值


算法步骤:
① 清除自环,输入的时候判断即可
② 先判断从固定根开始是否可达所有原图中的点。简单搜索加标记位就可以。如果不可就不用说了,肯定没戏。
③ 为除根之外的每个点选定一条最小入边。
(记pre [vi]为该边的起点)
④ 判断这个入边集是否存在有向环,如果不存在,我们很容易证明这个集合就是该图的最小树形图,转⑥,否则接⑤(利用prev数组,枚举为检查过的点作为搜索的起点,做类似DFS的操作)
⑤ 消环。设(u,i,w)表示从u到i的权为w的边。设刚才的有向环缩为新结点new。若u位于环上,并设环中指向u的边权是in[u]。那么对于每条从u出发的边(u, i, w),在新图中连接(new, i, w)的边,其中new为新加的人工顶点; 对于每条进入u的边(i, u, w),在新图中建立边(i, new, w-in[u])的边。新图中最小树形图的权加上旧图中被收缩的那个环的权和,就是原图中最小树形图的权。重复③④⑤
⑥ 成功,返回DMST总权值。
补充1:如果无固定根,增加一个节点,连接到所有节点,并且距离一样,即可转化为有固定根。
补充2:本算法只能求最小总权值,但不能求路径。


tju 2248 http://acm.tju.edu.cn/toj/showp2248.html

裸的最小树形图

<span style="font-family:KaiTi_GB2312;font-size:18px;">#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 1010
#define MAXM 42010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int Read()
{char c = getchar();while (c < '0' || c > '9') c = getchar();int x = 0;while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x;
}void Print(int a)
{if(a>9)Print(a/10);putchar(a%10+'0');
}struct Edge
{int u,v;int cost;
}edge[MAXM];
int pre[MAXN],vis[MAXN],id[MAXN];
int in[MAXN];int zhuliu(int root,int n,int m,Edge edge[])
{int res=0;int u,v;while(1){for(int i=0;i<n;i++)in[i]=INF;for(int i=0;i<m;i++)if(edge[i].u!=edge[i].v&&(edge[i].cost-in[edge[i].v]<eps)){pre[edge[i].v]=edge[i].u;in[edge[i].v]=edge[i].cost;}for(int i=0;i<n;i++)if(i!=root&&in[i]==INF)return -1;int tn=0;MEM(id,-1); MEM(vis,-1);in[root]=0;for(int i=0;i<n;i++){res+=in[i];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]=tn;id[v]=tn++;}}if(tn==0) break;//没有有向环for(int i=0;i<n;i++)if(id[i]==-1)id[i]=tn++;for(int i=0;i<m;){v=edge[i].v;edge[i].u=id[edge[i].u];edge[i].v=id[edge[i].v];if(edge[i].u!=edge[i].v)edge[i++].cost-=in[v];elseswap(edge[i],edge[--m]);}n=tn;root=id[root];}return res;
}
int g[MAXN][MAXN];
int x[MAXN],y[MAXN];int main()
{
//    fread;int n,m;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0) break;for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=INF;int u,v,cost;while(m--){scanf("%d%d%d",&u,&v,&cost);u--; v--;if(u==v) continue;g[u][v]=min(g[u][v],cost);}int num=0;for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(g[i][j]<INF){edge[num].u=i;edge[num].v=j;edge[num++].cost=g[i][j];}int ans=zhuliu(0,n,num,edge);if(ans==-1) printf("impossible\n");else printf("%d\n",ans);}return 0;
}
</span>

UVA 11183 http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18548

<span style="font-family:KaiTi_GB2312;font-size:18px;">#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 1010
#define MAXM 42010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int Read()
{char c = getchar();while (c < '0' || c > '9') c = getchar();int x = 0;while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x;
}void Print(int a)
{if(a>9)Print(a/10);putchar(a%10+'0');
}struct Edge
{int u,v;int cost;
}edge[MAXM];
int pre[MAXN],vis[MAXN],id[MAXN];
int in[MAXN];int zhuliu(int root,int n,int m,Edge edge[])
{int res=0;int u,v;while(1){for(int i=0;i<n;i++)in[i]=INF;for(int i=0;i<m;i++)if(edge[i].u!=edge[i].v&&(edge[i].cost-in[edge[i].v]<eps)){pre[edge[i].v]=edge[i].u;in[edge[i].v]=edge[i].cost;}for(int i=0;i<n;i++)if(i!=root&&in[i]==INF)return -1;int tn=0;MEM(id,-1); MEM(vis,-1);in[root]=0;for(int i=0;i<n;i++){res+=in[i];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]=tn;id[v]=tn++;}}if(tn==0) break;//没有有向环for(int i=0;i<n;i++)if(id[i]==-1)id[i]=tn++;for(int i=0;i<m;){v=edge[i].v;edge[i].u=id[edge[i].u];edge[i].v=id[edge[i].v];if(edge[i].u!=edge[i].v)edge[i++].cost-=in[v];elseswap(edge[i],edge[--m]);}n=tn;root=id[root];}return res;
}
int g[MAXN][MAXN];
int x[MAXN],y[MAXN];int main()
{
//    fread;int tc;int cs=1;scanf("%d",&tc);while(tc--){int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=INF;int u,v,cost;while(m--){scanf("%d%d%d",&u,&v,&cost);if(u==v) continue;g[u][v]=min(g[u][v],cost);}int num=0;for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(g[i][j]<INF){edge[num].u=i;edge[num].v=j;edge[num++].cost=g[i][j];}int ans=zhuliu(0,n,num,edge);printf("Case #%d: ",cs++);if(ans==-1) printf("Possums!\n");else printf("%d\n",ans);}return 0;
}
</span>

poj 3164 http://poj.org/problem?id=3164

此题中cost是两个点之间的距离 

<span style="font-family:KaiTi_GB2312;font-size:18px;">#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 1010
#define MAXM 12010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int Read()
{char c = getchar();while (c < '0' || c > '9') c = getchar();int x = 0;while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x;
}void Print(int a)
{if(a>9)Print(a/10);putchar(a%10+'0');
}struct Edge
{int u,v;double cost;
}edge[MAXM];
int pre[MAXN],vis[MAXN],id[MAXN];
double in[MAXN];double zhuliu(int root,int n,int m,Edge edge[])
{double res=0;int u,v;while(1){for(int i=0;i<n;i++)in[i]=INF;for(int i=0;i<m;i++)if(edge[i].u!=edge[i].v&&(edge[i].cost-in[edge[i].v]<eps)){pre[edge[i].v]=edge[i].u;in[edge[i].v]=edge[i].cost;}for(int i=0;i<n;i++)if(i!=root&&in[i]==INF)return -1;int tn=0;MEM(id,-1); MEM(vis,-1);in[root]=0;for(int i=0;i<n;i++){res+=in[i];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]=tn;id[v]=tn++;}}if(tn==0) break;//没有有向环for(int i=0;i<n;i++)if(id[i]==-1)id[i]=tn++;for(int i=0;i<m;){v=edge[i].v;edge[i].u=id[edge[i].u];edge[i].v=id[edge[i].v];if(edge[i].u!=edge[i].v)edge[i++].cost-=in[v];elseswap(edge[i],edge[--m]);}n=tn;root=id[root];}return res;
}
double g[MAXN][MAXN];
int x[MAXN],y[MAXN];double dis(int u,int v)
{return sqrt((double)((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v])));
}int main()
{
//    fread;int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=INF;for(int i=0;i<n;i++)scanf("%d%d",&x[i],&y[i]);while(m--){int u,v;scanf("%d%d",&u,&v);u--; v--;if(u==v) continue;double len=dis(u,v);if(g[u][v]-len>eps)g[u][v]=len;}int num=0;for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(g[i][j]<INF){edge[num].u=i; edge[num].v=j; edge[num++].cost=g[i][j];}double ans=zhuliu(0,n,num,edge);if(ans==-1) printf("poor snoopy\n");else printf("%.2lf\n",ans);}return 0;
}
</span>



这篇关于最小树形图(tju 2248 UVA 11183 poj 3164)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1064341

相关文章

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10055 uva 10071 uva 10300(水题两三道)

情歌两三首,水题两三道。 好久没敲代码了为暑假大作战热热身。 uva 10055 Hashmat the Brave Warrior 求俩数相减。 两个debug的地方,一个是longlong,一个是输入顺序。 代码: #include<stdio.h>int main(){long long a, b;//debugwhile(scanf("%lld%lld", &

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直