首页 > ACM题库 > HDU-杭电 > HDU 1836 Another Convex Polygon Problem-最短路径-[解题报告] C++
2013
12-23

HDU 1836 Another Convex Polygon Problem-最短路径-[解题报告] C++

Another Convex Polygon Problem

问题描述 :

You are given a convex polygon with N vertices and M straight lines which divide the polygon into several regions. You must compute the number of regions into which the polygon is divided by the straight lines.

输入:

The first line of input contains the number T of test cases. The next lines describe the T test cases. The first line of each test case contains two integer numbers, separated by one blank: the number N of vertices of the convex polygon (3 <= N <= 10) and the number M of straight lines (0 <= M <= 10). The next N lines contain 2 integer numbers X and Y, denoting the coordinates of some vertex of the polygon. The vertices are given in clockwise or anti-clockwise order. Each of the next M lines contains 4 integer numbers: x1 y1 x2 y2. (x1,y1) and (x1,y1) are two different points on the straight line. All the X and Y coordinates in the input file are in the range -20…20.

输出:

For each test case print a line having the following format: “Number of regions=XXX.”, where XXX is replaced by the number of regions into which the polygon is divided.

样例输入:

2
3 0
0 0
1 1
1 0
3 3
0 0
1 1
1 0
1 2 3 4
1 2 3 4
1 2 3 4

样例输出:

Number of regions=1.
Number of regions=1.

最短路径的水题,不过我贡献了若干个WA,只因为题目里M,N坑爹的含义没仔细看——通常N是结点个数……,于是我代码中的一个字母错了,然后就悲剧了……

PS 我之所以把抽取最小值的ex_min()单拿出来是因为这样容易用堆优化。

/*
 * hdu-1863
 * mike-w
 * 2012-4-13
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_SIZE 128
#define INF (2<<25)
#define min(x,y) ((x)>(y)?(y):(x))

int dst[MAX_SIZE];
int tag[MAX_SIZE];
int f[MAX_SIZE][MAX_SIZE];
int N,M;

int ex_min(void)
{
	int i,x;
	for(x=-1,i=1;i<=M;i++)
		if(!tag[i] && dst[i]<INF)
			break;
	for(x=i++;i<=M;i++)
		if(!tag[i] && dst[i]<dst[x])
			x=i;
	return x<=M?x:-1;
}

int random_start(void)
{
	int i,j;
	for(i=1;i<=M;i++)
		for(j=1;j<=M;j++)
			if(f[i][j]>0)
				return i;
	return -1;
}

int prim(void)
{
	int i,x,cost;
	int start=random_start();
	if(start==-1)
		return -1;
	for(i=1;i<=M;i++)
		dst[i]=f[start][i],tag[i]=0;
	cost=0;
	while((x=ex_min())!=-1)
	{
		tag[x]=1;
		cost+=dst[x];
		for(i=1;i<=M;i++)
			if(!tag[i] && f[x][i]<INF && dst[i]>f[x][i])
				dst[i]=f[x][i];
	}
	for(i=1;i<=M;i++)
		if(!tag[i])
			cost=-1;
	return cost;
}

int main(void)
{
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
#endif
	int i,j,cost,e1,e2,e3;
	while(scanf("%d",&N),N)
	{
		scanf("%d",&M);
		for(i=1;i<=M;i++)
			for(j=1;j<=M;j++)
				f[i][j]=(i==j?0:INF);
		for(i=1;i<=N;i++)
		{
			scanf("%d%d%d",&e1,&e2,&e3);
			f[e1][e2]=f[e2][e1]=min(f[e1][e2],e3);
		}
		if(N>0)
			cost=prim();
		else
			cost=0;
		if(cost==-1)
			puts("?");
		else
			printf("%d\n",cost);
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/creativewang/article/details/7459429


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)