cần giúp đở giải quyết bài toán trênn http://acm.timus.ru

[quangtanck]

bạn nào làm bài này rùi giúp mình với.
acm.timus.ru/problem.aspx?space=1&num=1272

cứ báo lổi Wrong answer.

[truonganpn]

bạn nào làm bài này rùi giúp mình với.
acm.timus.ru/problem.aspx?space=1&num=1272

cứ báo lổi Wrong answer.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <float.h>
#include <iostream>
#include <conio.h>



#define MAX 100
int SoCanh=0;
bool V[MAX]; 

struct GRAPH
{
	int n;//chi so thanh pho
	int k;//so duong ham
	int m;//so cau
	int a[MAX][MAX];
};
typedef struct
{
	int v1;
	int v2;
	int w;
}EDGE;

EDGE T[MAX];

void NhapMaTran(GRAPH &g)
{
	
		//printf("Nhap vao so thanh pho:\t"); 
		scanf("%d",&g.n);
		//printf("So duong ham :"); 
		scanf("%d",&g.k);
		//printf("So duong cau :"); 
		scanf("%d",&g.m);
		
                // khoi tao ma tran vuong nxn voi cac gia tri la 0.
		for(int i = 0; i<g.n; i++)
		{
			for(int j = 0; j<g.n; j++)
			{
				g.a[i][j] = 0;
			}
		}

		int canh;

                // cap nhat lai gia tri tuong ung cho duong ham

		for (int i=0;i<g.k;i++)
		{
			scanf("%d",&canh);
			int x = (canh % 10);
			int y = int(canh/10);
			g.a[x-1][y-1]=g.a[y-1][x-1]=1;
		}

              // cap nhat lai gia tri tuong ung cho duong ham

		for (int i=0;i<g.m;i++)
		{
			scanf("%d",&canh);
			int x = (canh % 10);
			int y = int(canh/10);
			g.a[x-1][y-1]=g.a[y-1][x-1]=2;
		}

}

void XuatMaTran(GRAPH &g)
{
	printf("%d\n", g.n);
	int i, j;
	for (i=0; i<g.n; i++)
	{
		for (j=0; j<g.n; j++)

		{
			printf( "%d\t", g.a[i][j]);	
		}
		printf("\n");

	}
}

void PrimAlg(GRAPH g)
{
	int nT = 0;
	//Gán tất cả các đỉnh là chưa xét
	for( int i = 0 ; i < g.n; i++)
	{
		V[i] = false;
	}
	//Gán đã xét cho đỉnh 0
	V[0] = true;
	//Bắt đầu vòng lặp
	while(nT < g.n - 1)
	{
		EDGE eMin;
		int iMinWeight = -1.0; // -1 nghĩa là chưa có cạnh min
		//duyệt tất cả các đỉnh i chưa được xét
		for(int i = 0 ; i < g.n; i++)
		{
			if(V[i] == false)
			{
				//duyệt tat ca cac j canh da xet roi
				for(int j = 0 ; j < g.n; j++)
				{
					if(V[j] == true && g.a[i][j] != 0)
					{
						if(iMinWeight == -1.0 || iMinWeight > g.a[i][j]) 
							//chọn cạnh (i;j) nếu có trọng số nhỏ hơn iMinWeight hiện tại
						{
							eMin.v1 = i;
							eMin.v2 = j;
							eMin.w = g.a[i][j];
							iMinWeight = g.a[i][j];
						}
					}
				}
			}
		}
		if(iMinWeight == -1.0)
		{
			printf("khong lien thong");
			break;
		}
		else
		{
			//them canh eMin vao cay khung
			T[nT] = eMin;
			nT++;
			//cập nhật đỉnh đã xét cho đỉnh v1
			V[eMin.v1] = true;
		}
	}
	SoCanh=nT;
}
void ShowBrigde(EDGE E[MAX], int nE)
{
	int i_Cau=0; // khoi tai bien luu so cau it nhat
	for(int i = 0 ; i < nE; i++)
	{
		if(E[i].w==2) 
		  i_Cau++;// Neu canh co trong so la 2 tuc la canh do la cay cau
	}
	printf("%d",i_Cau);	
}
void main()
{

	GRAPH g;
	NhapMaTran(g);
	//printf("Ma tran ke\n");
	//XuatMaTran(g);
	PrimAlg(g);
	ShowBrigde(T,SoCanh);
}

Em trình bày hướng giải của mình đi, chứ để một đống code không có diễn giải như thế này làm sao mọi người có hứng thú mà đọc.

[08520001]

Bài này cho số đảo là N giay cao co nam.

[quangtanck]

Em trình bày hướng giải của mình đi, chứ để một đống code không có diễn giải như thế này làm sao mọi người có hứng thú mà đọc.

Bài toán trên em giải quyết bằng cách gắn trọng số cho đường hầm =1 và cầu = 2, sau đó dùng thuật toán prim để tìm đường đi ngắn nhất. khi đó số cầu sẻ là ít nhất vì trọng số lớn hơn, cần thiết lắm mới dùng cầu. sau khi tim được cây khung rùi em đếm trọng số của câu khung đấy có bao nhiêu cạnh =2 rùi xuất kq đó ra.

em test với dử liệu nhỏ thì đúng.nhưng khi up code lên trang acm thì sai mất. Mong được giúp đở.

[quangtanck]

theo hướng dẩn của anh em đã viết code lại như sau. nhưng sao vẩn không được a ơi. cứ Wrong answer hoài. mong anh chỉ giúp.
em code lại như sau:

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <conio.h>
#include<ctime>
#include <time.h>
#include <dos.h>
#include <iostream>
using namespace std;


#define MAX 100

struct graph
{
int n;//chi so thanh pho
int k;//so duong ham
int m;//so cau
int a[MAX][MAX];
int dinhnhan[MAX];
int sodao;
};


void NhapMaTranKe(graph &g)
{//printf("Nhap vao so thanh pho:\t");
scanf("%d",&g.n);
//printf("So duong ham :");
scanf("%d",&g.k);
//printf("So duong cau :");
scanf("%d",&g.m);
//printf("Nhap cac cap thanh pho theo thu tu:\n");

for(int i = 0; i<g.n; i++)
{
for(int j = 0; j<g.n; j++)
{
g.a[i][j] = 0;
}
}

int s;
for (int i=0;i<g.k;i++)
{
scanf("%d",&s);
int x = (s % 10);
int y = int(s/10);
g.a[x-1][y-1]=1;
}
for (int i=0;i<g.m;i++)
{
scanf("%d",&s);
int x = (s % 10);
int y = int(s/10);
g.a[x-1][y-1]=0;
}
}
void XuatMaTranKe(graph &g)
{
printf("%d\t",g.n);
int i,j;
for(i=0;i<g.n;i++)
{
printf("\n");
for(j=0;j<g.n;j++)
printf("%d ",g.a[i][j]);
}
}


//ham ViSit
void thamdao(graph &g,int i,int sodao)
{
g.dinhnhan[i] = sodao;

for(int j = 0; j < g.n; j++)
{
if((g.dinhnhan[j]==0)&&(g.a[i][j]||g.a[j][i]))
{
//goi lai ham dequy ViSit de gan nhan cho tat ca cac dinh
thamdao(g,j,sodao);
}
}
}
//hàm xét liên thông
int XetLienThong(graph &g,int &sodao)
{
for(int i =0;i<g.n;i++)//gan tat ca cac dinhnhan cua do thi = 0.
{
g.dinhnhan[i] = 0;
}
sodao = 0;
for(int i=0;i<g.n;i++)// chay den tat ca cac dinh cua do thi
{

if(g.dinhnhan[i]== 0 )//
{
sodao++;//tang nhandinh len.
thamdao(g,i,sodao);
}

}
return sodao;
}

void main ()
{
graph g;

NhapMaTranKe(g);
//XuatMaTranKe(g);

int label = 0;
int tplt=XetLienThong(g,label);
//InThanhPhanLienThong(g,tplt);
int kq = tplt -1;
printf ("%d",kq);


}

[08520001]

cái ma trận của em ah, nếu muốn dùng ma trận kề để lưu thì MAX phải là 10000
Với lúc em nhập, sao em chỉ scanf(
geox.

[10520355]

Code cho bạn. Ngắn gọn xúc tích, dễ hiểu. Đã accepted.
Đáp án là số vùng liên thông -1 ( bỏ các cạnh nối bởi bridges đi nha, chỉ giữ phần các cạnh nối bởi tunnels )

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vii;
int n,k,m;
vii a; // luu do thi
vi dfs_mark; // mang danh dau

void nhapdothi()
{
	int x,y;
        a.clear();
    	scanf("%d%d%d",&n,&k,&m);
    	a = vii(n);
    	dfs_mark.assign(n,-1);
    	for(int i=0; i<k; i++)
    	    	{
    	    		scanf("%d%d",&x,&y);
    	    		a[x-1].push_back(y-1);
    	    		a[y-1].push_back(x-1);
    	    	}
}
// duyet do thi theo chieu sau
void dfs(int u)
{
    dfs_mark[u]=0;
    for(unsigned int j=0; j<a[u].size(); j++)
    {
        int v= a[u][j];
        if(dfs_mark[v]==-1) dfs(v);
    }
}

int main()
{
	nhapdothi();
	int count=0;
	for(int i=0; i<n; i++)
	{
		if(dfs_mark[i]==-1)
		{
			dfs(i);
			count++;
		}
	}
	printf("%d",count-1);
	return 0;
}

[quangtanck]

Code cho bạn. Ngắn gọn xúc tích, dễ hiểu. Đã accepted.
Đáp án là số vùng liên thông -1 ( bỏ các cạnh nối bởi bridges đi nha, chỉ giữ phần các cạnh nối bởi tunnels )

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vii;
int n,k,m;
vii a; // luu do thi
vi dfs_mark; // mang danh dau

void nhapdothi()
{
	int x,y;
        a.clear();
    	scanf("%d%d%d",&n,&k,&m);
    	a = vii(n);
    	dfs_mark.assign(n,-1);
    	for(int i=0; i<k; i++)
    	    	{
    	    		scanf("%d%d",&x,&y);
    	    		a[x-1].push_back(y-1);
    	    		a[y-1].push_back(x-1);
    	    	}
}
// duyet do thi theo chieu sau
void dfs(int u)
{
    dfs_mark[u]=0;
    for(unsigned int j=0; j<a[u].size(); j++)
    {
        int v= a[u][j];
        if(dfs_mark[v]==-1) dfs(v);
    }
}

int main()
{
	nhapdothi();
	int count=0;
	for(int i=0; i<n; i++)
	{
		if(dfs_mark[i]==-1)
		{
			dfs(i);
			count++;
		}
	}
	printf("%d",count-1);
	return 0;
}

code của anh Cao Văn Nhàn chạy tuyệt thật, gọn nhưng có đề anh viết bằng vector em đọc mập mờ quá anh. anh có để chuyển bài này sang ma trận giúp được không anh. em chưa học về vector và chưa dùng bao giờ.

em cảm ơn anh nhiều !!

[10520355]

Vector cũng như mảng thôi, có điều vector thì không cần phải biết trước số lượng phần tử của nó, cho nên tối ưu không gian lưu trữ.
Lúc trước anh cũng sử dụng mảng, nhưng cái nào hay hơn thì sử dụng thôi. Em nên tìm hiểu nó.

http://cplusplus.com/reference/stl/

Trong phần STL của C++, nếu em nên biết mấy cái đó sẽ giúp cải thiện tốc độ rất nhiều và nhiều thứ khác nữa.
Trong các bài đồ thị, thường anh toàn sử dụng pair với vector không à. Sử dụng mảng tốn không gian nhớ và thời gian duyệt bị chậm lại đó em.

[quangtanck]

Vector cũng như mảng thôi, có điều vector thì không cần phải biết trước số lượng phần tử của nó, cho nên tối ưu không gian lưu trữ.
Lúc trước anh cũng sử dụng mảng, nhưng cái nào hay hơn thì sử dụng thôi. Em nên tìm hiểu nó.

http://cplusplus.com/reference/stl/

Trong phần STL của C++, nếu em nên biết mấy cái đó sẽ giúp cải thiện tốc độ rất nhiều và nhiều thứ khác nữa.
Trong các bài đồ thị, thường anh toàn sử dụng pair với vector không à. Sử dụng mảng tốn không gian nhớ và thời gian duyệt bị chậm lại đó em.

void dfs(int u)
{
dfs_mark[u]=0;
for(unsigned int j=0; j<a[u].size(); j++)
{
int v= a[u][j];
if(dfs_mark[v]==-1) dfs(v);
}
}

cái chổ J<a[u].size() này là sao anh, j sẻ chạy đến đâu là dừng vậy anh.?? em ko hiểu.

hihi. Nếu có thêm code bằng ma trận thì có thể đối chiếu qua lại, em nghĩ việc hiểu vector sẽ nhanh hơn, bây giờ mới bắt đầu tiếp xúc với vector kể cũng khó khăn lắm anh. anh có giúp em ! em cảm ơn nhìu!

[08520001]

Em phải hiểu là bài này, em dùng cấu trúc dữ liệu là ma trận kề, và nếu dùng cách đó, em sẽ không thể làm được bài này.
Còn cách sử dụng vector của bạn Nhàn là dùng cấu trúc dữ liệu danh sách kề, (Ma trận kề và danh sách kề là 2 cấu trúc dữ liệu trong đồ thị), nên mới Accept được.
shop giay nam.