java實作第五屆藍橋杯供水設施

供水設施

X星球的居民點很多。Pear決定修建一個浩大的水利工程，以解決他管轄的N個居民點的供水問題。現在一共有N個水塔，同時也有N個居民點，居民點在北側從1号到N号自西向東排成一排；水塔在南側也從1号到N号自西向東排成一排。

N條單向輸水線（有水泵動力），将水從南側的水塔引到北側對應的居民點。

我們不妨将居民點和水塔都看做平面上的點，居民點坐标為(1,K)(N,K)，水塔為(1,0)(N,0)。

除了N條縱向輸水線以外，還有M條單向的橫向輸水線，連接配接(Xi,Yi)和(Xi,(Yi)+1)或者(Xi,Yi)和(Xi,(Yi)-1)。前者被稱為向右的水路，而後者是向左的。不會有兩條水路重疊，即便它們方向不同。

布局的示意圖如：【p1.png】所示。

顯然，每個水塔的水都可以到達若幹個居民點（而不僅僅是對應的那個）。例如上圖中，4号水塔可以到達3、4、5、6四個居民點。

現在Pear決定在此基礎上，再修建一條橫向單項輸水線。為了友善考慮，Pear認為這條水路應當是自左向右的，也就是連接配接了一個點和它右側的點（例如上圖中連接配接5和6兩個縱線的橫向水路）。

Pear的目标是，修建了這條水路之後，能有盡可能多對水塔和居民點之間能到達。換句話說，設修建之後第i個水塔能到達Ai個點，你要最大化A1+A2+…+An。

根據定義，這條路必須和X軸平行，但Y坐标不一定要是整數。注意：雖然輸入中沒有重疊的水路，但是你的方案可以将新修的輸水線路與已有的水路重疊。

【輸入資料】

輸入第一行包含三個正整數N，M，K，含義如題面所述：N是縱向線數，M橫向線數，K是居民點縱坐标。

接下來M行，每行三個整數。前兩個正整數Xi Yi表示水路的起點坐标；

1<=Xi<=N,0<Yi<K。

接下來一個數0或者1，如果是0表示這條水路向左，否則向右。

保證水路都是合法的，也就是不會流向沒有定義的地方。

【輸出資料】

輸出一行。是一個正整數，即：題目中要求的最大化的A1+A2+…+An。

【輸入樣例1】

4 3 2

1 1 1

3 1 0

3 1 1

【輸出樣例1】

11

【輸入樣例2】

7 9 4

2 3 0

7 2 0

6 3 1

6 1 0

2 1 1

3 3 1

5 2 0

2 2 1

7 1 0

【輸出樣例2】

21

【資料範圍】

對于20%的資料，N,K<=20，M<=100

對于40%的資料，N,K<=100，M<=1000

對于60%的資料，N,K<=1000，M<=100000

對于100%的資料，N,K<=50000，M<=100000

資源約定：

峰值記憶體消耗（含虛拟機） < 256M

CPU消耗 < 5000ms

請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入…” 的多餘内容。

所有代碼放在同一個源檔案中，調試通過後，拷貝送出該源碼。

注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。

注意：主類的名字必須是：Main，否則按無效代碼處理。

import java.util.Scanner;

public class Main {
    public static int n, m , k;
    public static int[][] value;
    
    public void getResult() {
        int max = Integer.MIN_VALUE;
        for(int i = 1;i < n;i++) {
            if(value[i][i+1] == 0) {
                value[i][i+1] = 1;
                int temp = 0;
                for(int k = 1;k <= n;k++) {
                    temp++;
                    int t = k - 1;
                    while(t >= 1) {  //尋找左邊連通水磊
                        if(value[t][t+1] == 1) {
                            temp++;
                            t--;
                        } else
                            break;
                    }
                    t = k + 1;
                    while(t <= n) {  //尋找右邊連通水磊
                        if(value[t][t-1] == 1) {
                            temp++;
                            t++;
                        } else
                            break;
                    }
                }
                max = Math.max(max, temp);
                value[i][i+1] = 0;
            }
        }
        System.out.println(max);
    }
    
    public static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        value = new int[n + 1][n + 1];
        for(int i = 0;i < m;i++) {
            int x = in.nextInt();
            @SuppressWarnings("unused")
            double y = in.nextDouble();
            int c = in.nextInt();
            if(c == 0)
                value[x][x - 1] = 1;   //單向向左連通
            else
                value[x][x + 1] = 1;    //單向向右連通
        }
        test.getResult();
    }
}