IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

> Задача на графах
Merhaba
сообщение 18.12.2011 9:41
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Добрый День!!! Помогите Пожалуйста разобраться с задачей: http://acm.timus.ru/problem.aspx?space=1&num=1709
Код на Си++:
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<map>
#include<time.h>
#include<string.h>
#include<string>
#include<iostream>
#include<queue>

#define N 105

int d, a;
int n;
bool used[N];
char g[N][N];
char ng[N][N];

void dfs(int v){    
  used[v] = 1;
  for(int i = 1; i <= n; i++)
    if(g[v][i] == '1' && !used[i]){
      ng[v][i] = ng[i][v] = '1';
      dfs(i);
    }
}

int main(void){
  scanf("%d", &n);
  scanf("%d%d ", &d, &a);
  for(int i = 1; i <= n; i++)
    gets(g[i] + 1), g[i][0] = '&';

  bool found = 0;         
  int mi = -1;
  for(int i = 1; i <= n && !found; i++)
    for(int j = 1;  j <= n && !found; j++)
      if(g[i][j] == '1')
        found = 1, mi = i;


  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      ng[i][j] = '0';

  //no flights
  if(mi == -1){
    long long ans = a * (n - 1);
    printf("%I64d\n", ans);
    
    for(int i = 1; i < n; i++)
      g[i][i+1] = g[i+1][i] = 'a';

    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++)
        printf("%c", g[i][j]);
      puts("");
    }
  }
  else{ //there are some flights
    long long ans_add(0);
    for(int i = mi; i <= n; i++)
      if(!used[i]){
        if(i != mi && g[i][mi] == '0') //connect components
          ng[i][mi] = ng[mi][i] = 'a', ans_add += a;
        
        dfs(i);
      }
    
    long long ans_del(0);
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= n; j++)
        if(g[i][j] == '1' && ng[i][j] == '0')
          ng[i][j] = 'd', ans_del += d;
        else if(g[i][j] == '1' && ng[i][j] == '1')
          ng[i][j] = '0';

    long long ans = ans_add + (ans_del / 2);
    printf("%I64d\n", ans);
    for(int i = 1; i <= n; i++){
      for(int j = 1; j <= n; j++)
        printf("%c", ng[i][j]);
      puts("");
    }
  }
 
  return 0;
}

Тимус прекрасно принял этот код!
Переписал этот код на Java:
import java.io.IOException;
import java.util.Scanner;


public class Main {
static char [][] g = new char[105][105];
static char [][] ng = new char[105][105];
static int [] used = new int[105];
static int n;

static void dfs(int v){
used[v] = 1;
for(int i = 1; i <= n; i++)
if((g[v][i] == '1') && (used[i] == 0)){
ng[v][i] = '1';
ng[i][v] = '1';
dfs(i);
}
}

public static void main(String[] args) throws IOException{
Scanner in = new Scanner(System.in);

int ans_add = 0;
n = in.nextInt();
int d = in.nextInt();
int a = in.nextInt();
char c;

for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
c = (char) System.in.read();
if(c == '\n')
c = (char) System.in.read();
g[i][j] = c;
ng[i][j] = '0';
}
/*System.out.println("Введённая матрица!");
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){System.out.print(g[i][j]);}
System.out.println();}*/

int found = 0;
int mi = -1;
for(int i = 0; (i <= n) && (found == 0); i++)
for(int j = 1; (j <= n) && (found == 0); j++)
if(g[i][j] == '1'){
found = 1;
mi = i;
}

if(mi == -1){
int ans = a * (n - 1);
System.out.println(ans);

for(int i = 1; i < n; i++){
g[i][i + 1] = 'a';
g[i + 1][i] = 'a';
}

for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
System.out.print(g[i][j]);
System.out.println();
}
}
else{
ans_add = 0;
for(int i = mi; i <= n; i++)
if(used[i] == 0){
if((i != mi) && (g[i][mi] == '0')){
ng[i][mi] = 'a';
ng[mi][i] = 'a';
ans_add += a;
}

dfs(i);
}
}

int ans_del = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if((g[i][j] == '1') && (ng[i][j] == '0')){
ng[i][j] = 'd';
ans_del += d;
}
else if((g[i][j] == '1') && (ng[i][j] == '1'))
ng[i][j] = '0';

int answ = ans_add + (ans_del / 2);
System.out.println(answ);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)
System.out.print(ng[i][j]);
System.out.println();
}
}
}

Почему-то выдаёт WA на первом же тесте(
Помогите Пожалуйста найти и устранить ошибку smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 2)
IUnknown
сообщение 18.12.2011 20:19
Сообщение #2


a.k.a. volvo877
*****

Группа: Пользователи
Сообщений: 1 013
Пол: Мужской

Репутация: -  627  +


Цитата
Почему-то выдаёт WA на первом же тесте(
Странно, правда?

У тебя где заканчивается Else, который соответствует if(mi == -1)? А в программе на С++ где он заканчивается, посмотри внимательно...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Merhaba
сообщение 18.12.2011 21:35
Сообщение #3


Пионер
**

Группа: Пользователи
Сообщений: 57
Пол: Мужской

Репутация: -  0  +


Цитата(IUnknown @ 18.12.2011 20:19) *

Странно, правда?

У тебя где заканчивается Else, который соответствует if(mi == -1)? А в программе на С++ где он заканчивается, посмотри внимательно...


import java.io.IOException;
import java.util.Scanner;


  public class Main {
	static char [][]  g = new char[105][105];
	static char [][] ng = new char[105][105];
	static int  [] used = new int[105];
	static int n;

	static void dfs(int v){
		used[v] = 1;
		for(int i = 1; i <= n; i++)
			if((g[v][i] == '1') && (used[i] == 0)){
				ng[v][i] = '1';
				ng[i][v] = '1';
				dfs(i);
			}
	}

	public static void main(String[] args) throws IOException{
		Scanner in = new Scanner(System.in);

		int ans_add = 0;
		n = in.nextInt();
		int d = in.nextInt();
		int a = in.nextInt();
		char c;

		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++){
				c = (char) System.in.read();
				if(c == '\n')
					c = (char) System.in.read();
			    g[i][j] = c;
				ng[i][j] = '0';
			}
                /*System.out.println("Введённая матрица!");
                for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){System.out.print(g[i][j]);}
                System.out.println();}*/

		int found = 0;
		int mi = -1;
		for(int i = 0; (i <= n) && (found == 0); i++)
			for(int j = 1; (j <= n) && (found == 0); j++)
				if(g[i][j] == '1'){
					found = 1;
					mi = i;
				}

		if(mi == -1){
			int ans = a * (n - 1);
			System.out.println(ans);

			for(int i = 1; i < n; i++){
				g[i][i + 1] = 'a';
				g[i + 1][i] = 'a';
			}

			for(int i = 1; i <= n; i++){
				for(int j = 1; j <= n; j++)
					System.out.print(g[i][j]);
				System.out.println();
			}
		}
		else{
			ans_add = 0;
			for(int i = mi; i <= n; i++)
				if(used[i] == 0){
					if((i != mi) && (g[i][mi] == '0')){
						ng[i][mi] = 'a';
						ng[mi][i] = 'a';
						ans_add += a;
					}

					dfs(i);
				
		}

		int ans_del = 0;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if((g[i][j] == '1') && (ng[i][j] == '0')){
					ng[i][j] = 'd';
					ans_del += d;
				}
				else if((g[i][j] == '1') && (ng[i][j] == '1'))
					ng[i][j] = '0';

		int answ = ans_add + (ans_del / 2);
		System.out.println(answ);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++)
				System.out.print(ng[i][j]);
			System.out.println();
		}
	}
}
}


Всё равно выдаёт неправильный ответ... Что на сей раз не так?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия 28.07.2025 18:04
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"