Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача на графах
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
Merhaba
Добрый День!!! Помогите Пожалуйста разобраться с задачей: 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
IUnknown
Цитата
Почему-то выдаёт WA на первом же тесте(
Странно, правда?

У тебя где заканчивается Else, который соответствует if(mi == -1)? А в программе на С++ где он заканчивается, посмотри внимательно...
Merhaba
Цитата(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();
}
}
}
}


Всё равно выдаёт неправильный ответ... Что на сей раз не так?
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.