程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1198 Farm Irrigation (並查集優化,構圖)

HDU 1198 Farm Irrigation (並查集優化,構圖)

編輯:C++入門知識

HDU 1198 Farm Irrigation (並查集優化,構圖)


本題和HDU暢通工程類似,只不過暢通工程給出了數的連通關系,

而此題需要自己判斷連通關系,即兩個水管是否可以連接到一起,也是本題的難點所在。

記錄狀態,不斷combine(),注意只需要判斷左方和上方就行,這樣不會重復判斷,而且肯定都可以遍歷到所有的狀態。

#include
#include
#include
//記錄水管的形狀,每種水管用一個由'0'和'1'組成的長度為4的字符串代表,
//分別表示上下左右四邊是否有接口,'0'無,'1'有
char a[11][5]={"1010","1001","0110","0101","1100","0011",
               "1011","1110","0111","1101","1111"};
int father[51][51];
char map[51][51];
int n,m;
using namespace std;
int find(int x)//查找父節點,並壓縮路徑
{
	if(father[x/n][x%n]!=x)
		father[x/n][x%n]=find(father[x/n][x%n]);
	return father[x/n][x%n];
}

void Union(int x,int y)//合並x,y的集合
{
	x=find(x);
	y=find(y);
	if(x!=y)
		father[y/n][y%n]=x;
}

void judge(int i,int j)//判斷map[i][j]和它的左側和上側是否連通,如連通則合並
{
	if(j>0&&a[map[i][j]-'A'][2]=='1'&&a[map[i][j-1]-'A'][3]=='1')//判斷上方
		Union(i*n+j,i*n+j-1);

	if(i>0&&a[map[i][j]-'A'][0]=='1'&&a[map[i-1][j]-'A'][1]=='1')//判斷左方
		Union(i*n+j,(i-1)*n+j);
}

int main()
{
	int i,j,count;
	while(scanf("%d%d",&m,&n)!=-1&&(n!=-1||m!=-1))
	{
		for(i=0;i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved