2888478_re.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {

    static int n, k, s, t, minc;
    static int c[][] = new int [110][110];
    static int w[][] = new int [110][110];
    static int f[][] = new int [110][110];
    static int v[] = new int [110];
    static int fa[] = new int [110];
    static int inf = 10000000;
    
    public static boolean Find_Way()
    {
        int i, j;
        boolean quit;
        
        for(i = 0; i < n; i++)
            v[i] = inf;
        v[s] = 0;
        do
        {
            quit = true;
            for(i = 0; i < n; i++)
            {
                if(v[i]<inf)
                {
                    for(j = 0; j < n; j++)
                    {
                        if(f[i][j]<c[i][j]&&v[i]+w[i][j]<v[j])
                        {
                            v[j] = v[i]+w[i][j];
                            fa[j] = i;
                            quit = false;
			}
                    }
                }
            }
        }while(!quit);
        if(v[t]<inf)
            return true;
        return false;
    }
    public static void Add_Way()
    {
        int i, j;

	i = t;
	do
	{
            j = i;
            i = fa[j];
            f[i][j]++;
            f[j][i] = -f[i][j];
	}while(i!=s);
	minc += v[t];
    }
    public static void main(String[] args) {
        
        Scanner cin = new Scanner (System.in);
        int i, j, num, id;
        
        n = cin.nextInt();
        k = cin.nextInt();
        for(i = 0; i < 110; i++)
        {
            for(j = 0; j < 110; j++)
            {
                c[i][j] = w[i][j] = f[i][j] = 0;
            }
        }
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < n; j++)
            {
                id = i*n+j;
                id = id*2+1;
                num = cin.nextInt();
                c[id][id+1] = 1;
                w[id][id+1] = -num;
                w[id+1][id] = num;
            }
        }
        id = n*n*2;
        c[0][1] = k;w[0][1] = w[1][0] = 0;
        c[id][id+1] = k;w[id][id+1] = w[id+1][id] = 0;
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < n; j++)
            {
                if(i!=n-1)
                {
                    c[(i*n+j+1)*2][((i+1)*n+j)*2+1] = inf;
                    c[(i*n+j)*2+1][((i+1)*n+j)*2+1] = inf;
                    c[(i*n+j+1)*2][((i+1)*n+j+1)*2] = inf;
                    c[(i*n+j)*2+1][((i+1)*n+j+1)*2] = inf;
                    w[(i*n+j)*2+1][((i+1)*n+j+1)*2] = w[((i+1)*n+j+1)*2][(i*n+j)*2+1] = 0;
                    w[(i*n+j+1)*2][((i+1)*n+j+1)*2] = w[((i+1)*n+j+1)*2][(i*n+j+1)*2] = 0;
                    w[(i*n+j)*2+1][((i+1)*n+j)*2+1] = w[((i+1)*n+j)*2+1][(i*n+j)*2+1] = 0;
                    w[(i*n+j+1)*2][((i+1)*n+j)*2+1] = w[((i+1)*n+j)*2+1][(i*n+j+1)*2] = 0;
                }
                if(j!=n-1)
                {
                    c[(i*n+j+1)*2][(i*n+j+1)*2+1] = inf;
                    c[(i*n+j+1)*2][(i*n+j+2)*2] = inf;
                    c[(i*n+j)*2+1][(i*n+j+1)*2+1] = inf;
                    c[(i*n+j)*2+1][(i*n+j+2)*2] = inf;
                    w[(i*n+j)*2+1][(i*n+j+2)*2] = w[(i*n+j+2)*2][(i*n+j)*2+1] = 0;
                    w[(i*n+j)*2+1][(i*n+j+1)*2+1] = w[(i*n+j+1)*2+1][(i*n+j)*2+1] = 0;
                    w[(i*n+j+1)*2][(i*n+j+2)*2] = w[(i*n+j+2)*2][(i*n+j+1)*2] = 0;
                    w[(i*n+j+1)*2][(i*n+j+1)*2+1] = w[(i*n+j+1)*2+1][(i*n+j+1)*2] = 0;
                }
            }
        }
        n = n*n*2+2;
        s = 0;t = n-1;
        minc = 0;
        while(Find_Way())
            Add_Way();
        System.out.println(minc*-1);
    }
}