Untitled

 avatar
unknown
plain_text
6 months ago
2.8 kB
4
Indexable
import java.util.*;

public class q2part {

    // Maksimum karı hesaplamak için kullanılan fonksiyon
    public static int maxProfit(int numLiquids, int numConversions, int[] prices, List<int[]> conversions) {
        // Sıvı türleri arasındaki dönüşümleri temsil etmek için bir graf oluşturun
        List<List<Integer>> graph = new ArrayList<>();
        
        // Grafın her sıvı için boş bir komşu listesi olacak şekilde başlatılması
        for (int i = 0; i < numLiquids; i++) {
            graph.add(new ArrayList<>());
        }

        // Geçişleri graf yapısına ekleyin
        for (int[] conversion : conversions) {
            int from = conversion[0] - 1; // Dizi 0 tabanlı, bu yüzden -1 yapıyoruz
            int to = conversion[1] - 1;
            graph.get(from).add(to);
        }

        // Başlangıçta maksimum fiyatları mevcut fiyatlara eşitleyin
        int[] maxPrices = Arrays.copyOf(prices, numLiquids);

        // Bellman-Ford algoritmasını kullanarak maksimum fiyatları güncelleyin
        for (int i = 0; i < numLiquids - 1; i++) {
            for (int u = 0; u < numLiquids; u++) {
                for (int v : graph.get(u)) {
                    // Eğer u'dan v'ye geçiş varsa, v'nin fiyatını güncelleyin
                    if (maxPrices[v] < maxPrices[u]) {
                        maxPrices[v] = maxPrices[u];
                    }
                }
            }
        }

        // Maksimum kar hesaplayın
        int maxProfit = 0;
        for (int i = 0; i < numLiquids; i++) {
            maxProfit = Math.max(maxProfit, maxPrices[i] - prices[i]);
        }

        return maxProfit;
    }

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

        // Test durumu sayısını al
        int testCases = scanner.nextInt();

        for (int t = 0; t < testCases; t++) {
            // Sıvı sayısı ve dönüşüm sayısını al
            int numLiquids = scanner.nextInt();
            int numConversions = scanner.nextInt();

            // Sıvı fiyatlarını al
            int[] prices = new int[numLiquids];
            for (int i = 0; i < numLiquids; i++) {
                prices[i] = scanner.nextInt();
            }

            // Dönüşüm bilgilerini al
            List<int[]> conversions = new ArrayList<>();
            for (int i = 0; i < numConversions; i++) {
                int from = scanner.nextInt();
                int to = scanner.nextInt();
                conversions.add(new int[]{from, to});
            }

            // Her test durumu için maksimum karı hesapla ve sonucu yazdır
            int result = maxProfit(numLiquids, numConversions, prices, conversions);
            }
}
}

Editor is loading...
Leave a Comment