Добрый День!!! Помогите Пожалуйста разобраться с задачей:
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 на первом же тесте(
Помогите Пожалуйста найти и устранить ошибку