阿祁的部落格

CSES 1695 -  Police Chase 解題心得( 題目 )

解題概念:Dinic max flow min cost

解題方法:這題需要用到flow的演算法，其中dinic可以以O(VE^2)求出一個網絡線的最大流，而min cost=max flow，藉由這個道理我們令題目每條邊的容量為1，找到的最大流=要把路堵住的最小成本。

//Author:En Chi Tsung(欉恩祁)

//Date:2022/04/13

import java.util.*;

import java.util.*;

import java.io.*;

public class cses1695 {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static int ret,rd,n,no=0;

    public static Queue<Integer> q=new LinkedList<>();

    public static ArrayList<ArrayList<Edge>> e=new ArrayList<>();

    public static int[] lv=new int[505];

    public static int[] c=new int[505];

    public static int[] fw=new int[2005];

    public static int[] vis=new int[2005];

    public static void main(String[] args) throws Exception{

        n=readint();

        final int m=readint();

        for(int i=0;i<=n;i++)e.add(new ArrayList<>());

        int a,b;

        for(int i=0;i<m;i++) {

            a=readint();

            b=readint();

            e.get(a).add(new Edge(b,no++));

            e.get(b).add(new Edge(a,no++));

        }

        int tot=dinic();

        bw.write(tot+"\n");

        find(1,1);

        find(n,2);

        for(int i=1;i<=n;i++) {

            for(Edge j:e.get(i)) {

                if((j.x&1)==0&&vis[i]!=0&&vis[j.n]!=0&&vis[i]!=vis[j.n]) {

                    bw.write(i+" "+j.n+"\n");

                }

            }

        }

        bw.flush(); 

    }

    

    public static int dinic() {

        int cnt=0,x;

        Arrays.fill(fw,1);

        while(true) {

            bfs();

            if(lv[n]==-1)break;

            while(true) {

                x=dfs(1,10000);

                if(x==0)break;

                cnt+=x;

            }

        }

        return cnt;

    }

    

    public static void bfs() {

        Arrays.fill(lv,-1);

        lv[1]=0;

        q.offer(1);

        int o;

        while(!q.isEmpty()) {

            o=q.poll();

            for(Edge i:e.get(o)) {

                if(lv[i.n]!=-1||fw[i.x]==0)continue;

                lv[i.n]=lv[o]+1;

                q.offer(i.n);

            }

        }

    }

    

    public static int dfs(int x,int f) {

        if(f==0||x==n)return f;

        int ret=0,d;

        for(Edge i:e.get(x)) {

            if(lv[i.n]==lv[x]+1) {

                d=dfs(i.n,Math.min(f,fw[i.x]));

                ret+=d;

                fw[i.x^1]+=d;

                fw[i.x]-=d;

                f-=d;

            }

        }

        return ret;

    }

    

    public static void find(int x,int dir) {

        vis[x]=dir;

        for(Edge i:e.get(x)) {

            if(vis[i.n]!=0||fw[i.x]==0)continue;

            find(i.n,dir);

        }

    }

    

    public static int readint() throws Exception{

        ret=0;

        rd=br.read();

        while(rd>47&&rd<58) {

            ret*=10;

            ret+=(rd&15);

            rd=br.read();

        }

        return ret;

    }

}

 

class Edge{

    int n,x;

    Edge(int a,int b){

        n=a;

        x=b;
    }
}