1273 Drainage Ditches

1273 Drainage Ditches

解答例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] network = new int[m][m];
            for(int i=0;i<m;i++) Arrays.fill(network[i], 0);
            
            for(int i=0;i<n;i++){
                int s = sc.nextInt() - 1;
                int e = sc.nextInt() - 1;
                int c = sc.nextInt();
                network[s][e] += c;
            }
            
            Solver sol = new Solver(m, 0, m-1, network);
            System.out.println(sol.solve());    
        }
    }
}

class Solver{
    int size;//number of nodes
    int source;//nodeID of source
    int sink;//nodeID of sink
    int[][] network;
    Solver(int n,int s,int t,int[][] net){
        size = n;
        source = s;
        sink = t;
        network = net;
    }
    public int solve(){
        List<Integer> path;
        int flow = 0;
        while(true){
            path = searchPath();
            if(path==null) break;
            
            //calculate how much flow increases
            int flowinc = Integer.MAX_VALUE;
            
            int prev = source;
            for(int v:path){
                flowinc = Math.min(flowinc,network[prev][v]);
                prev = v;
            }
            
            //flow increases
            flow += flowinc;
            
            //update network array
            prev = source;
            for(int v:path){
                network[prev][v] -= flowinc;
                network[v][prev] += flowinc;
                prev = v;
            }
        }
        
        return flow;
    }
    
    //search shortest path from source to sink by BFS
    private List<Integer> searchPath(){
        int[] prev = new int[size];
        Arrays.fill(prev, -1);
        
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(source);
        
        L : while(!q.isEmpty()){
            int u = q.poll();
            for(int i=0;i<size;i++){
                if(prev[i]==-1&&network[u][i]>0){
                    prev[i] = u;
                    
                    //discoverd path to sink
                    if(i==sink) break L;
                    
                    q.offer(i);
                }
            }
        }
        
        if(prev[sink]==-1) return null;
        else return getPath(prev);
    }
    
    //get path to sink from pred node array
    private List<Integer> getPath(int[] prev){
        LinkedList<Integer> path = new LinkedList<Integer>();
        int u = sink;
        while(u!=source){
            path.addFirst(u);
            u = prev[u];
        }
        return path;
    }
}

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2006年05月14日 00:01
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。