首页 > ACM题库 > HDU-杭电 > HDU 1827 Summer Holiday-连通性问题-[解题报告] C++
2013
12-23

HDU 1827 Summer Holiday-连通性问题-[解题报告] C++

Summer Holiday

问题描述 :

To see a World in a Grain of Sand
And a Heaven in a Wild Flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
                  ―― William Blake

听说lcy帮大家预定了新马泰7日游,Wiskey真是高兴的夜不能寐啊,他想着得快点把这消息告诉大家,虽然他手上有所有人的联系方式,但是一个一个联系过去实在太耗时间和电话费了。他知道其他人也有一些别人的联系方式,这样他可以通知其他人,再让其他人帮忙通知一下别人。你能帮Wiskey计算出至少要通知多少人,至少得花多少电话费就能让所有人都被通知到吗?

输入:

多组测试数组,以EOF结束。
第一行两个整数N和M(1<=N<=1000, 1<=M<=2000),表示人数和联系对数。
接下一行有N个整数,表示Wiskey联系第i个人的电话费用。
接着有M行,每行有两个整数X,Y,表示X能联系到Y,但是不表示Y也能联系X。

输出:

输出最小联系人数和最小花费。
每个CASE输出答案一行。

样例输入:

12 16
2 2 2 2 2 2 2 2 2 2 2 2 
1 3
3 2
2 1
3 4
2 4
3 5
5 4
4 6
6 4
7 4
7 12
7 8
8 7
8 9
10 9
11 10

样例输出:

3 6

 

 

 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<math.h>
#define N 1010
#define inf 10000000
using namespace std;
inline int Min(int a,int b){return a>b?b:a;}

struct node{
	int from, to, nex;
}edge[N*5];
int head[N], edgenum;
void addedge(int u, int v){
	node E={u,v,head[u]};
	edge[ edgenum ] = E;
	head[u] = edgenum++;
}
int DFN[N], Low[N], Time, vis[N], sign, belong[N];
int Stack[N], top;
void tarjan(int u, int fa){
	DFN[ u ] = Low[ u ] = Time++;
	vis[ u ] = 1;
	Stack[top++] = u;
	int child = 0;
	for(int i = head[u]; i!=-1; i = edge[i].nex){
		int v = edge[i].to;
		if(DFN[ v ] == -1){
			tarjan(v, u);
			Low[u] = Min(Low[u], Low[v]);
		}
		/*else if(fa == v){
			if(child) Low[u] = Min(Low[u], DFN[v]);
			child++;
		}*/
		else if(vis[v])//v是走过的点 -> 这是反向弧
			Low[u] = Min(Low[u], DFN[v]);
	}
	if(DFN[u] == Low[u])//反向弧在u及u以下
	{
		sign++;
		while(1){
			int now = Stack[--top];
			vis[now] = 0;
			belong[now] = sign;
			if(now == u)break;
		}
	}
}

void tarjan_init(){
		memset(head, -1, sizeof(head)); edgenum = 0;
		memset(DFN, -1, sizeof(DFN));
		memset(Low, -1, sizeof(Low));
//		memset(belong, 0, sizeof(belong));
		memset(vis, 0, sizeof(vis));
		sign = top = 0;
		Time = 0;
}
int a[N], n, m;
int lala[N], inde[N];

int main(){
	int i,j,u,v;
	while(~scanf("%d %d",&n,&m)){
		tarjan_init();

		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		while(m--){
			scanf("%d %d",&u,&v);
			addedge(u, v);
		}
		for(i=1;i<=n;i++)if(DFN[i]==-1)tarjan(i, -1);

		int ans1 = 0, ans2 = 0;
		memset(inde, 0, sizeof(inde));
		for(i = 0;i<edgenum; i++)
		{
			u = edge[i].from; v = edge[i].to;
			if(belong[u] != belong[v])
				inde[ belong[v] ] ++;
		}
		for(i = 1; i <= sign;i++)
		{
			if(inde[i] == 0)
				ans1++;
			lala[i] = inf;
		}
		for(i = 1; i <= n;i++)
		{
			int tmp = belong[i];
			if(inde[ tmp ] == 0)
				lala[tmp] = Min(lala[tmp], a[i]);
		}
		for(i = 1; i <= sign; i++)
			if(lala[i] != inf)
				ans2 += lala[i];

		printf("%d %d\n",ans1,ans2);
	}
	return 0;
}

 

解题报告转自:http://blog.csdn.net/acmmmm/article/details/16354183


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。