POJ 3164 最小树形图裸题

题意:

给定n个点 m条有向边(点标从1开始)

下面n个点坐标

下面m条边

 

问最小树形图权值(无则输出一句话)

思路:最小树形图裸题

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
/*
* 最小树形图
* 复杂度O(NM)
* 点从0开始
*/
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 40010;
struct Edge{
	int u,v;
	double cost;
}edge[MAXM];
int pre[MAXN],id[MAXN],visit[MAXN];
double in[MAXN];
double zhuliu(int root,int n,int m,Edge edge[])
{
	int u,v;
	double res=0;
	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])
			{
				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;
			memset(id,-1,sizeof(id));
			memset(visit,-1,sizeof(visit));
			in[root] = 0;
			for(int i = 0;i < n;i++)
			{
				res += in[i];
				v = i;
				while( visit[v] != i && id[v] == -1 && v != root)
				{
					visit[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];
				else
					swap(edge[i],edge[--m]);
			}
			n = tn;
			root = id[root];
	}
	return res;
}
double dis[105][105];
struct node{
	double x,y;
}p[105];
double Dis(node a, node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int n, m;
int main()
{
	int i, j, u, v; double d;
	while(~scanf("%d %d", &n, &m)){
		for(i = 0; i < n; i++)
			{
				scanf("%lf%lf",&p[i].x,&p[i].y);
				for(j = 0; j < n; j++)dis[i][j] = INF;
		}
		while(m--){
			scanf("%d%d",&u,&v); u--, v--;
			dis[u][v] = min(dis[u][v], Dis(p[u],p[v]));
		}
		int edgenum = 0;
		for(i = 0; i < n; i++)if(i!=j)
			for(j = 0; j < n; j++)if(dis[i][j]<INF)
			{
				Edge E={i,j,dis[i][j]};
				edge[edgenum++] = E;
			}
		d = zhuliu(0,n,edgenum,edge);
		if(d<0)puts("poor snoopy");
		else printf("%.2lf\n", d);
	}	
	return 0;
}


 

POJ 3164 最小树形图裸题

上一篇:读书笔记-容器深入理解


下一篇:solr使用的一点记录