Posted 04/06/2016Updated 07/19/2023 Semprathlon / Simfae Dean ACM-ICPCan hour read (About 7280 words)

ACM竞赛Java模板[dev-160504]

ACM-ICPC

Java Code Template By Semprathlon

部分理论知识引用自维基百科

Input 输入

An enhanced InputReader supporting keeping reading data until the end of input while the number of input cases is unknown:
一个加强版的输入器 ，支持读到输入文件末尾的方式，用法类似java.util.Scanner但效率显著提高:

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public boolean hasNext() {
        return tokenizer != null && tokenizer.hasMoreTokens() || nextLine() != null;
    }

    public String nextLine() {
        String tmp = null;
        try {
            tmp = reader.readLine();
            tokenizer = new StringTokenizer(tmp);
        } catch (IOException e) {
            throw new RuntimeException(e);
        } catch (NullPointerException e) {
            return null;
        }
        return tmp;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Keeping reading data until the end of input：
读取数据直至文件末尾：

import java.io.*;
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InputReader in = new InputReader(System.in);
		while (in.hasNext()) {
                    // TODO ...
		}
	}

}

Output 输出

import java.io.PrintWriter;

PrintWriter out = new PrintWriter(System.out);
// TODO ...
out.flush(); // 更新缓冲区，使输出生效
out.close();

Data Structure 数据结构篇

Pair 二元组

Pair.make_pair(TypeA left,TypeB right)可构造一个二元组对象并返回，不必指定类型。
比较大小时默认先比较left，若left相同则再比较right。

class Pair<TypeA extends Comparable<TypeA>, TypeB extends Comparable<TypeB>> implements Comparable<Pair<TypeA, TypeB>> {
	TypeA left;
	TypeB right;

	public Pair() {
	}

	public Pair(TypeA first, TypeB second) {
		left = first;
		right = second;
	}

	public static <TypeA extends Comparable<TypeA>, TypeB extends Comparable<TypeB>> Pair<TypeA, TypeB> make_pair(
			TypeA first, TypeB second) {
		return new Pair<TypeA, TypeB>(first, second);
	}

	public String toString() {
		return "[" + left.toString() + "," + right.toString() + "]";
	}

	boolean equals(Pair<TypeA, TypeB> p) {
		return this.left.equals(p.left) && this.right.equals(p.right);
	}

	public int compareTo(Pair<TypeA, TypeB> p) {
		if (this.left.equals(p.left))
			return this.right.compareTo(p.right);
		return this.left.compareTo(p.left);
	}
}

另一种比较器写法：


class Pair_Comp<TypeA extends Comparable<TypeA>, TypeB extends Comparable<TypeB>>
		implements Comparator<Pair<TypeA, TypeB>> {
	public int compare(Pair<TypeA, TypeB> p1, Pair<TypeA, TypeB> p2) {
		return p1.compareTo(p2);
	}
}

Queue 队列

1	Queue<integer> que = new LinkedList<integer>();

用法详见SPFA等应用。

Priority Queue 优先队列

It is not recommended to use,for the constructor with the parameter of a comparator is supported since jdk 1.8.

1	Queue<Integer> que = new PriorityQueue<Integer>();

Heap 堆

This is a minimum heap:
这是一个小根堆：

class Heap {
    private int maxn;
    int[] data;
    int r;
 
    Heap(int size) {
        maxn=size;
        data = new int[maxn];
        r = 0;
    }
    
    void clear(){
        //Arrays.fill(data, 0);
        r=0;
    }
    
    public int size() {
        return r;
    }
 
    void swap(int a, int b) {
        int tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }
 
    void up(int p) {
        if (!(p > 0))
            return;
        int q = p >> 1;
        if (data[p] < data[q]) {
            swap(p, q);
            up(q);
        }
    }
 
    void down(int p) {
        int q;
        if ((p << 1) >= r)
            return;
        else if ((p << 1) == r - 1) {
            q = p << 1;
        } else {
            q = (data[p << 1] < data[p << 1 | 1] ? p << 1 : p << 1 | 1);
        }
        if (data[p] > data[q]) {
            swap(p, q);
            down(q);
        }
    }
 
    void push(int n) {
        data[r++] = n;
        up(r - 1);
    }
 
    int pop() {
        int res = data[0];
        swap(0, r - 1);
        r--;
        down(0);
        return res;
    }
 
    int top() {
        return data[0];
    }
    
}

Directional edge 有向边

class Edge {
	int v, f, w, nx;

	Edge() {
	}

	Edge(int _v, int _f, int _w, int _nx) {
		modify(_v, _f, _w, _nx);
	}

	void modify(int _v, int _f, int _w, int _nx) {
		v = _v;
		f = _f;
		w = _w;
		nx = _nx;
	}
}

Arc 弧

适用于网络流模型中的有向边。

class Edge {
	int to, cap, flow, next;

	Edge() {
	}

	Edge(int _v, int _f, int _w, int _nx) {
		modify(_v, _f, _w, _nx);
	}

	void modify(int _v, int _f, int _w, int _nx) {
		to = _v;	cap = _f;	flow = _w;	next = _nx;
	}
};

Adjacent Table 链式前向星（邻接表）

避免重复分配内存空间设计。
addEdge根据具体需求修改。

class Graph {
	int[] h;
	int maxn, maxm;
	Edge[] e;
	int num;

	Graph(int _n, int _m) {
		maxn = _n;
		maxm = _m;
		h = new int[maxn];
		e = new Edge[maxm];
		for (int i = 0; i < maxm; i++)
			e[i] = new Edge();
	}

	void init() {
		Arrays.fill(h, -1);
		num = 0;
	}

	void addEdge(int u, int v, int f, int w) {
		e[num].modify(v, f, w, h[u]);
		h[u] = num++;
		e[num].modify(u, 0, -w, h[v]);
		h[v] = num++;
	}
}

ST table ST表

RMQ 区间最值查询（静态，离线）

void RMQ(){ //initializing->O(nlogn){
    for(int i = 1; i != maxm; ++i)
        for(int j = 1; j <= n; ++j)
            if(j + (1 << i) - 1 <= n){
                maxsum[i][j] = Math.max(maxsum[i - 1][j], 
                            maxsum[i - 1][j + (1 << i >> 1)]);
                minsum[i][j] = Math.min(minsum[i - 1][j], 
                            minsum[i - 1][j + (1 << i >> 1)]);
                }
    }
     
int query(int src,int des){
        int k = (int)(Math.log(des - src + 1.0) / Math.log(2.0));
        int maxres = Math.max(maxsum[k][src], 
                          maxsum[k][des - (1 << k) + 1]);
        int minres = Math.min(minsum[k][src], 
                          minsum[k][des - (1 << k) + 1]);
        return maxres-minres;
    }

Segment Tree 线段树

单点更新，区间求和。

class SegTree {
    int l, r, m;
    long val;
    SegTree L, R;

    SegTree() {
    }

    SegTree(int x, int y) {
        build(x, y);
    }

    void build(int x, int y) {
        int mi = (x + y) >> 1;
        l = x;
        r = y;
        m = mi;
        val = 0;
        if (x < y) {
            if (L == null)
                L = new SegTree(x, m);
            else
                L.build(x, m);

            if (R == null)
                R = new SegTree(m + 1, y);
            else
                R.build(m + 1, y);
        }
    }

    void up() {
        val = L.val + R.val;
    }

    void add(int x, int v) {
        if (l == r) {
            val += v;
            return;
        }
        if (x <= m)
            L.add(x, v);
        else if (x > m)
            R.add(x, v);
        up();
    }

    long query(int x, int y) {
        if (x <= l && r <= y) {
            return val;
        }
        long res = 0;
        if (x <= m)
            res += L.query(x, y);
        if (y > m)
            res += R.query(x, y);
        return res;
    }
}

Binary Indexed Tree 树状数组

Suppose there are n distinct integers ranging from $ 1$ to $ n$,and the $ k$th largest one is required(use query(k-1)).
假设有范围在 $ [1,n]$内的 $ n$个不同整数，求第 $ k$大的数（调用query(k-1)）。

class BIT {
    int[] data;
    int sz;

    BIT() {
    }

    BIT(int _sz) {
        sz = _sz;
        data = new int[sz + 1];
    }

    int lowbit(int x) {
        return x & (-x);
    }

    void add(int p, int v) {
        while (p <= sz) {
            data[p] += v;
            p += lowbit(p);
        }
    }

    int sum(int p) {
        int res = 0;
        while (p > 0) {
            res += data[p];
            p -= lowbit(p);
        }
        return res;
    }

    int find(int p) {
        int l = 1, r = sz;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (sum(mid) <= p)
                l = mid + 1;
            else
                r = mid;
        }

        return l;
    }
}

Graph Theory 图论篇

Topological Sorting 拓扑排序

int[] degree;
boolean[][] arc;
Vector<Integer> ans;
PriorityQueue<Integer> que;

void Topo(int n) {
        for (int u = 1; u <= n; u++)
            if (degree[u] == 0) {
                que.add(u);
            }
        while (!que.isEmpty()) {
            int u = que.poll();
            ans.add(u);
            for (int v = 1; v <= n; v++) {
                if (arc[u][v]) {
                    degree[v]--;
                    if (degree[v] == 0) {
                        que.add(v);
                    }
                }
            }
        }
}

Hungarian Algorithm 二分图最大匹配 - 匈牙利算法

先初始化，再通过init执行清理。
输入左点与右点个数之和与连接左点、右点之边，求最大匹配数。

class Hungary {
	private int n, maxn;
	private Vector<Integer>[] vec;
	private int[] match;
	private boolean[] vis;

	public Hungary(int _n) {
		maxn = _n;
		vec = new Vector[maxn];
		for (int i = 0; i < maxn; i++)
			vec[i] = new Vector<Integer>();
		match = new int[maxn];
		vis = new boolean[maxn];
	}

	void init(int _n) {
		n = _n;
		for (int i = 0; i < n; i++)
			vec[i].clear();

	}

	void addEdge(int u, int v) {
		vec[u].add(v);
		vec[v].add(u);
	}

	boolean dfs(int v) {
		vis[v] = true;
		for (int i = 0; i < vec[v].size(); i++) {
			int u = vec[v].get(i);
			int w = match[u];
			if (w < 0 || !vis[w] && dfs(w)) {
				match[v] = u;
				match[u] = v;
				return true;
			}
		}
		return false;
	}

	int matching() {
		int res = 0;
		Arrays.fill(match, -1);
		for (int i = 0; i < n; i++)
			if (match[i] < 0) {
				Arrays.fill(vis, false);
				if (dfs(i))
					res++;
			}
		return res;
	}
}

Hopcroft-Karp Algorithm 二分图最大匹配 - HK算法

class HK {
	private int inf = 0x3fffffff;
	private int n, n1, n2, maxn;
	private Vector<Integer>[] vec;
	private int[] mx, my, dx, dy;
	private boolean[] vis;
	private Queue<Integer> que;
	private int dis;

	public HK(int _n) {
		maxn = _n;
		vec = new Vector[maxn];
		for (int i = 0; i < maxn; i++)
			vec[i] = new Vector<Integer>();
		mx = new int[maxn];
		my = new int[maxn];
		vis = new boolean[maxn];
		que = new LinkedList<Integer>();
		dx = new int[maxn];
		dy = new int[maxn];
	}

	void init(int _n, int _n1, int _n2) {
		n = _n;	n1 = _n1;	n2 = _n2;
		for (int i = 0; i < n; i++)
			vec[i].clear();

	}

	void addEdge(int u, int v) {
		vec[u].add(v);
		vec[v].add(u);
	}

	boolean searchpath() {
		que.clear();
		dis = inf;
		Arrays.fill(dx, -1);
		Arrays.fill(dy, -1);
		for (int i = 0; i < n1; i++) {
			if (mx[i] == -1) {
				que.add(i);
				dx[i] = 0;
			}
		}
		while (!que.isEmpty()) {
			int u = que.poll();
			if (dx[u] > dis)
				break;
			for (int i = 0; i < vec[u].size(); i++) {
				int v = vec[u].get(i);
				if (dy[v] == -1) {
					dy[v] = dx[u] + 1;
					if (my[v] == -1)
						dis = dy[v];
					else {
						dx[my[v]] = dy[v] + 1;
						que.add(my[v]);
					}
				}
			}
		}
		return dis != inf;
	}

	boolean findpath(int u) {
		for (int i = 0; i < vec[u].size(); i++) {
			int v = vec[u].get(i);
			if (!vis[v] && dy[v] == dx[u] + 1) {
				vis[v] = true;
				if (my[v] != -1 && dy[v] == dis)
					continue;
				if (my[v] == -1 || findpath(my[v])) {
					my[v] = u;
					mx[u] = v;
					return true;
				}
			}
		}
		return false;
	}

	int maxmatch() {
		int res = 0;
		Arrays.fill(mx, -1);
		Arrays.fill(my, -1);
		while (searchpath()) {
			Arrays.fill(vis, false);
			for (int i = 0; i < n1; i++)
				if (mx[i] == -1)
					res += findpath(i) ? 1 : 0;
		}
		return res;
	}
}

SPFA最短路径

先通过构造函数初始化，再通过init执行清理。

class spfa {
	final int inf = 0x3fffffff;
	private int maxn, maxm, src;
	public Graph g;
	private Queue<Integer> que;
	private boolean[] inQue;
	public int[] dis;
	public int[] prev, pree;

	public spfa(int _n, int _m) {
		maxn = _n;
		maxm = _m;
		dis = new int[maxn];
		inQue = new boolean[maxn];
		prev = new int[maxn];
		pree = new int[maxn];
		que = new LinkedList<Integer>();
	}

	void init(Graph _g, int _u) {
		g = _g;
		src = _u;
	}

	void init(int _u) {
		if (g == null)
			g = new Graph(maxn, maxm);
		g.init();
		src = _u;
	}

	void addEdge(int u, int v, int f, int w) {
		g.addEdge(u, v, f, w);
	}

	void solve() {
		que.clear();
		que.add(src);
		Arrays.fill(dis, inf);
		dis[src] = 0;
		inQue[src] = true;
		while (!que.isEmpty()) {
			int u = que.poll();
			for (int i = g.h[u]; i != -1; i = g.e[i].nx) {
				if (g.e[i].f > 0 && dis[u] + g.e[i].w < dis[g.e[i].v]) {
					dis[g.e[i].v] = dis[u] + g.e[i].w;
					prev[g.e[i].v] = u;
					pree[g.e[i].v] = i;
					if (!inQue[g.e[i].v]) {
						inQue[g.e[i].v] = true;
						que.add(g.e[i].v);
					}
				}
			}
			inQue[u] = false;
		}
	}

	int get_res(int v) {
		solve();
		return dis[v];
	}
}

Number Theory 数论篇

Extended Euclid Theorem 扩展欧几里得定理

Suppose $ ax+by=gcd(a,b) $,and the value of $ x $ and of $ y $ are required.
已知 $ ax+by=gcd(a,b) $，求 $ x$与 $ y$的值。
注意 $ x$与 $ y$中很可能有一个是负整数。

long x,y;
void extgcd(long a, long b) {
        if (b == 0L) {
            x = 1L;
            y = 0L;
            return;
        }
        extgcd(b, a % b);
        long t = x;
        x = y;
        y = t - a / b * y;
}

Modular multiplicative inverse 模逆元

$ a^{-1} \equiv b \pmod{n},a \cdot a^{-1} \equiv 1 $.
The modular multiplicative inverse of $ a $ modulo $ m $ can be found with the extended Euclidean algorithm.
设exdgcd(a,n)为扩展欧几里得算法的函数，则可得到 $ ax+ny=gcd(a,n)$.
若 $ g=1$，则该模逆元存在，根据结果 $ ax+ny=1$.
在 $ \mod{n}$之下， $ ax+ny \equiv ax \equiv 1 $，根据模逆元的定义，此时$ x$即为$ a$关于模$ n$的其中一个模逆元。
事实上， $ x+kn(k \in \mathbb{Z}) $都是 $ a$关于模 $ n$的模逆元，这里取最小的正整数解 $ x\mod{n} (x \lt n) $。
若 $ g\ne 1$，则该模逆元不存在。

long cal_inv(long n, long mod) {
        extgcd(n, mod);
        return x < 0L ? (x + mod) % mod : x % mod;
}

According to Euler’s theorem, if $ a$ is coprime to $ m$, that is, $ gcd(a, m) = 1$, then $ a^φ(m)≡1\pmod{m}$,where $ φ(m)$ is Euler’s totient function.
$ a^{φ(m)-1}≡a^{-1}\pmod{m}$.
In the special case when $ m$ is a prime, the modular inverse is given by the below equation as: $ a^{-1}≡a^{m-2}\pmod{m}$.
欧拉函数求单个逆元：

1
2
3

long cal_inv(long n, long mod) {
        return pow_mod(n, phi[mod] - 1, mod);
}

通过递推的方式，在线性时间复杂度内求出若干个逆元：

void cal_inv(int maxn, long mod) {
        inv[1] = 1;
        for (int i = 2; i < maxn; i++)
            inv[i] = (mod - mod / i) * inv[(int) (mod % i)] % mod;
}

Quick power and modulo 快速幂取模

To calculate $ n^m%mod $:
计算 $ n^m%mod $：

long pow_mod(long n, long m, long mod) {
        long res = 1L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                res = res * n % mod;
            n = n * n % mod;
            m >>= 1;
        }
        return res;
}

Multiply and modulo 乘法取模

To calculate $ nm%mod $:
在$ n $和$ m $的值都较大，直接相乘会溢出的情况下，计算 $ nm%mod $：

long mul_mod(long n, long m, long mod) {
        long ans = 0L;
        n %= mod;
        while (m > 0L) {
            if ((m & 1L) > 0L)
                ans = (ans + n) % mod;
            m >>= 1;
            n = (n + n) % mod;
        }
        return ans;
}

Division and modulo 除法取模

To calculate $ n/m%mod $ correctly ( $ mod$ is a prime number thus $ φ(mod)=mod-1 $).
利用欧拉函数计算 $ n/m%mod $（当 $ mod$是一个质数时有 $ φ(mod)=mod-1 $）：

long div_mod(long n, long m, long mod) {
        return n * pow_mod(m, mod - 2, mod) % mod;
        // return n * pow_mod(m, phi(mod) - 1, mod) % mod;
}

In other words,use modular multiplicative inverse.
或者直接使用模逆元：

1
2
3

long div_mod(long n, long m, long mod) {
        return n * inv[(int) m] % mod;
}

Factorial and modulo 阶乘取模

void Get_Fac(long n, long mod) {
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i;
            fac[i] %= mod;
        }
}

Prime filtering (linear) 线性筛质数

int[] pri,fstp;
    void filter_prime(){
        pri=new int[maxn];
        fstp=new int[maxn];
        for(int i=2;i<maxn;i++){
            if (fstp[i]==0){
                pri[++pri[0]]=i;
            }
            for(int j=1;j<=pri[0]&&i*pri[j]<maxn;j++){
                int k=i*pri[j];
                fstp[k]=pri[j];
            }
        }
    }

Calculating Euler function $ φ(n) $ 求欧拉函数值

int[] pri,phi,fstp;
    void cal_euler(){
        pri=new int[maxn];
        fstp=new int[maxn];
        phi=new int[maxn];
        phi[1]=1;
        for(int i=2;i<maxn;i++){
            if (fstp[i]==0){
                pri[++pri[0]]=i;
                phi[i]=i-1;
            }
            for(int j=1;j<=pri[0]&&i*pri[j]<maxn;j++){
                int k=i*pri[j];
                fstp[k]=pri[j];
                if (i%pri[j]==0){
                    phi[k]=phi[i]*pri[j];
                    break;
                }
                else{
                    phi[k]=phi[i]*(pri[j]-1);
                }
            }
        }
    }

Calculating Möbius function $ μ(n) $ 求莫比乌斯函数值

莫比乌斯函数$ μ(d) $的定义如下：

若$ d=1 $，那么$ μ(d)=1 $；
若$ d=p_1p_2…p_k $($ p_1…p_k $均为互异质数)，那么$ μ(d)=(−1)^k $；
其他情况下，$ μ(d)=0 $.

int[] pri,fstp,miu;
    void cal_euler(){
        pri=new int[maxn];
        fstp=new int[maxn];
        miu=new int[maxn];
        miu[1]=1;
        for(int i=2;i<maxn;i++){
            if (fstp[i]==0){
                pri[++pri[0]]=i;
                miu[i]=-1;
            }
            for(int j=1;j<=pri[0]&&i*pri[j]<maxn;j++){
                int k=i*pri[j];
                fstp[k]=pri[j];
                if (i%pri[j]==0){
                    miu[k]=0;
                    break;
                }
                else{
                    miu[k]=-miu[i];
                }
            }
        }
    }

Integer Prime Factorization 分解质因数

Vector<Integer> get_prime_factor(int n){
        Vector<Integer> res=new Vector<Integer>();
        res.clear();
        for(int i=2;i*i<=n;i++)
            if (n%i==0){
                res.add(i);
                while(n%i==0)
                    n/=i;
            }
        if (n>1) res.add(n);
        return res;
}

Quick Greatest Common Divisor 快速求最大公约数

int kgcd(int a, int b) {
        if (a == 0)
            return b;
        if (b == 0)
            return a;
        if ((a & 1) == 0 && (b & 1) == 0)
            return kgcd(a >> 1, b >> 1) << 1;
        else if ((b & 1) == 0)
            return kgcd(a, b >> 1);
        else if ((a & 1) == 0)
            return kgcd(a >> 1, b);
        else
            return kgcd(Math.abs(a - b), Math.min(a, b));
}

Chinese Remainer Theorem 中国剩余定理

Resolving $ \begin{cases} x ≡a_1 \pmod{m_1}, \newline x ≡a_2 \pmod{m_2}, \newline …, \newline x ≡a_n \pmod{m_n}. \end{cases} $.
解同余方程组 $ \begin{cases} x ≡a_1 \pmod{m_1}, \newline x ≡a_2 \pmod{m_2}, \newline …, \newline x ≡a_n \pmod{m_n}. \end{cases} $。

long CRT(long n, long[] a, long[] m) {
        long pro = 1L, res = 0L;
        for (int i = 0; i < n; i++)
            pro *= m[i];
        for (int i = 0; i < n; i++) {
            long w = pro / m[i];
            extgcd(m[i], w);
            res = (res + mul_mod(y, mul_mod(w, a[i], pro), pro)) % pro;
        }
        return (res + pro) % pro;
}

Combinatorial Mathematics 组合数学篇

Combination Calculation #1 组合数计算1

$ C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$.

double[][] c;
void init(){
        c=new double[maxn][maxn];
        c[0][0]=1;
        for(int i=1;i<maxn;i++){
            c[i][0]=c[i][i]=1;
            for(int j=1;j<i;j++)
                c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
}

Combination Calculation #2 组合数计算2

It is guaranteed that $ n≥m$,but $ n!$ should be computed in advance.
在 $ n≥m$且 $ n!$已求出的前提下，单个计算 $ C_n^m$：

long C(long n, long m, long mod) {
        int a = (int) (n % mod), b = (int) (m % mod);
        return div_mod(fac[a], mul_mod(fac[a - b], fac[b], mod), mod);
}

Lucas Theorem 卢卡斯定理

C(n, m, mod) refers to $ C_n^m%mod $.
C(n, m, mod)表示 $ C_n^m%mod $。

如果有
$ n = a_k p^k + a_{k-1} p^{k-1} + … + a_1 p + a_0 $,
$ m = b_k p^k + b_{k-1} p^{k-1} + … + b_1 p + b_0 $,
则$ C_n^m = \prod_{i=0}^k C_{a_i}^{b_i}%p $.

long Lucas(long n, long m, long mod) {
        long ret = 1L;
        while (n > 0L && m > 0L) {
            if (n % mod < m % mod)
                return 0L;
            ret = mul_mod(ret, C(n, m, mod), mod);
            ret %= mod;
            n /= mod;
            m /= mod;
        }
        return ret;
}

Catalan number 卡塔兰数

$ C_n = {2n\choose n} - {2n\choose n+1} = {1\over n+1}{2n\choose n} \quad\text{ for }n\ge 0$;
The Catalan numbers satisfy the recurrence relation $ C_0 = 1 \quad $ and $ \quad C_{n+1}=\sum_{i=0}^{n}C_i,C_{n-i}\quad\text{for }n\ge 0 $;
moreover, $ C_n= \frac 1{n+1} \sum_{i=0}^n {n \choose i}^2$.
Asymptotically, the Catalan numbers grow as $ C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$.
组合数学中有非常多的组合结构可以用卡塔兰数来计数。

$ C_n$表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
将上例的X换成左括号，Y换成右括号， $ C_n$表示所有包含n组括号的合法运算式的个数：((())) ()(()) ()()() (())() (()())
$ C_n$表示有n个节点组成不同构二叉树的方案数。
$ C_n$表示有2n+1个节点组成不同构满二叉树（full binary tree）的方案数。

证明：
令1表示进栈，0表示出栈，则可转化为求一个2n位、含n个1、n个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含n个1、n个0的2n位二进制数共有 $ {2n \choose n}$个，下面考虑不满足要求的数目。
考虑一个含n个1、n个0的2n位二进制数，扫描到第2m+1位上时有m+1个0和m个1（容易证明一定存在这样的情况），则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0，则对应一个n+1个0和n-1个1的二进制数。反之亦然（相似的思路证明两者一一对应）。
从而 $ C_n = {2n \choose n} - {2n \choose n + 1} = \frac{1}{n+1}{2n \choose n}$。证毕。

$ C_n$表示所有在n × n格点中不越过对角线的单调路径的个数。一个单调路径从格点左下角出发，在格点右上角结束，每一步均为向上或向右。计算这种路径的个数等价于计算Dyck word的个数：X代表“向右”，Y代表“向上”。
$ C_n$表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。
$ C_n$表示对{1, …, n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, …, n),其中S（w）递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。
$ C_n$表示集合{1, …, n}的不交叉划分的个数.那么, Cn永远不大于第n项贝尔数. Cn也表示集合{1, …, 2n}的不交叉划分的个数，其中每个段落的长度为2。
$ C_n$表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。
$ C_n$表示表为2×n的矩阵的标准杨氏矩阵的数量。也就是说，它是数字 1, 2, …, 2n 被放置在一个2×n的矩形中并保证每行每列的数字升序排列的方案数。同样的，该式可由勾长公式的一个特殊情形推导得出。

本例中使用递推公式 $ C_1=1,C_n=\frac{(4n-2)}{(n+1)} \cdot C_{n-1}$;

long C[];
void get_Catalan(int maxn) {
        C[1] = 1;
        for (int i = 2; i < maxn - 1; i++) {
            C[i] = C[i - 1] * ((i << 2) - 2) % mod;
            C[i] = div_mod(C[i], i + 1, mod);
        }
}

Stirling numbers of the 1st kind 第一类斯特灵数

The Stirling numbers of the first kind are the coefficients in the expansion $ x_{n} = \sum_{k=0}^n s(n,k) x^k $.
where $ x_{n} $ (a Pochhammer symbol) denotes the falling factorial, $ x_{n}=x(x-1)(x-2)\cdots(x-n+1) $.
第一类Stirling数是有正负的，其绝对值是n个元素的项目分作k个环排列的方法数目。

给定$ s(n,0)=0 $,$ s(1,1)=1 $，有递归关系$ s(n,k)=s(n-1,k-1) + (n-1) s(n-1,k) $.

递推关系的说明：考虑第$ n $个物品，$ n $可以单独构成一个非空循环排列，这样前$ n-1 $种物品构成$ k-1 $个非空循环排列，有$ s(n-1,k-1) $种方法；也可以前$ n-1 $种物品构成k个非空循环排列，而第$ n $个物品插入第$ i $个物品的左边，这有$ (n-1)*s(n-1,k) $种方法。

Stirling numbers of the 2nd kind 第二类斯特灵数

第二类Stirling数是n个元素的集定义k个等价类的方法数目。

给定$ S(n,n)=S(n,1)=1 $，有递归关系$ S(n,k) = S(n-1,k-1) + k S(n-1,k) $

递推关系的说明：考虑第n个物品，n可以单独构成一个非空集合，此时前n-1个物品构成k-1个非空的不可辨别的集合，有$ S(n-1,k-1) $种方法；也可以前n-1种物品构成k个非空的不可辨别的集合，第n个物品放入任意一个中，这样有$ k*S(n-1,k) $种方法。
$ S(n,n-1)=C(n,2)=n(n-1)/2 $
$ S(n,2)=2^{n-1} - 1 $
$ S(n,k) =\frac{1}{k!}\sum_{j=1}^{k}(-1)^{k-j} C(k,j) j^n $
$ C(k,j) $是二项式系数。

#2-dimensional Computational Geometry 平面计算几何篇
double pi = Math.acos(-1.0);
double eps = 1e-3;

Double Comparing 实数的比较

1
2
3

int dcmp(double d) {
    return (d > eps ? 1 : 0) - (d < -eps ? 1 : 0);
}

Degree/Radian 角度/弧度互化

double Rad2Deg(double rad) {
    return rad * 180.0 / pi;
}

double Deg2Rad(double deg) {
    return deg * pi / 180.0;
}

Point 点

类定义

class Point {
    double x, y;

    Point() {
    }

    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }

    Point(Point p) {
        this(p.x, p.y);
    }

    static class Comp implements Comparator<Point> {
        Point prep;

        Comp(Point p) {
            prep = p;
        }

        public int compare(Point a, Point b) {
            double tmp = Point.cross(prep, a, b);
            if (dcmp(tmp) == 0)
                return -dcmp(dist(a, prep) - dist(b, prep));
            return -dcmp(tmp);
        }
}

函数计算

判断相等

1
2
3

public boolean equals(Point p) {
    return dcmp(Math.sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y))) == 0;
}

求两点间的欧氏距离

1
2
3

double dist(Point a, Point b) {
    return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

两点取中点

1
2
3

Point mid(Point a, Point b) {
    return new Point((a.x + b.x) / 2.0, (a.y + b.y) / 2.0);
}

Vector 向量

类定义

class Vector extends Point {
    Vector() {
    }

    Vector(double _x, double _y) {
        x = _x;
        y = _y;
    }

    Vector(Point a, Point b) {
        this(b.x - a.x, b.y - a.y);
    }

    Vector(Point p) {
        this(p.x, p.y);
}}

基本运算

Point add(Point r) {
    return new Point(x + r.x, y + r.y);
}

Point sub(Point r) {
    return new Point(x - r.x, y - r.y);
}

Point mul(double r) {
    return new Point(x * r, y * r);
}

Point move(double dx, double dy) {
    return new Point(x + dx, y + dy);
}

Point rotate(double a) {
    return new Point(x * Math.cos(a) - y * Math.sin(a), x * Math.sin(a) + y * Math.cos(a));
}

Point rotate(double dx, double dy, double a) {
    return this.move(-dx, -dy).rotate(a).move(dx, dy);
}

Vector normal() {
    double len = this.length();
    return new Vector(-y / len, x / len);
}

函数计算

求点积

1
2
3

double dot(Vector r) {
        return x * r.x + y * r.y;
}

求叉积

1
2
3

double cross(Vector r) {
        return x * r.y - y * r.x;
}

求向量的模

1
2
3

double length() {
        return Math.sqrt(this.dot(this));
}

求不共线的三点所成角$ \angle AOB$:

1
2
3

double angle(Point o, Point a, Point b) {
        return angle(new Vector(o, a), new Vector(o, b));
}

1
2
3

double angle(Vector a, Vector b) {
        return Math.acos(dot(a, b) / a.length() / b.length());
}

1
2
3

double angle(Point a, Point b) {
        return angle(new Vector(a), new Vector(b));
}

Line 直线/线段

类定义

class Line extends Vector {
    Point s, e;

    Line() {
    }

    Line(Point _s, Point _e) {
        s = _s;
        e = _e;
    }

    Line(double x1, double y1, double x2, double y2) {
        this(new Point(x1, y1), new Point(x2, y2));
    }

    Vector vector() {
        return new Vector(s, e);
    }

}

关系判断

判断直线相交


boolean isLineInter(Line l1, Line l2) {
        if (l1.s.equals(l1.e) || l2.s.equals(l2.e))
            return false;
        return dcmp(cross(l2.s, l1.s, l1.e) * cross(l2.e, l1.s, l1.e)) <= 0;
    }

判断线段相交


boolean isSegInter(Point s1, Point e1, Point s2, Point e2) {
    if (dcmp(Math.min(s1.x, e1.x) - Math.max(s2.x, e2.x)) <= 0
            && dcmp(Math.min(s1.y, e1.y) - Math.max(s2.y, e2.y)) <= 0
            && dcmp(Math.min(s2.x, e2.x) - Math.max(s1.x, e1.x)) <= 0
            && dcmp(Math.min(s2.y, e2.y) - Math.max(s1.y, e1.y)) <= 0
            && dcmp(Vector.cross(s2, e2, s1) * Vector.cross(s2, e2, e1)) <= 0
            && dcmp(Vector.cross(s1, e1, s2) * Vector.cross(s1, e1, e2)) <= 0)
        return true;
    return false;
}

boolean isSegInter2(Point p1, Point p2, Point p3, Point p4) // vigorous intersection
{
    return dcmp(cross(p3, p4, p1)) * dcmp(cross(p3, p4, p2)) == -1;
}

boolean isSegInter(Line l1, Line l2) {
    return isSegInter(l1.s, l1.e, l2.s, l2.e);
}

boolean isSegInter2(Line l1, Line l2) {
    return isSegInter2(l1.s, l1.e, l2.s, l2.e);
}

函数计算

求两直线交点


Point GetLineIntersection(Point p, Vector v, Point q, Vector w) {
       Vector u = new Vector(p.sub(q));
       double t = cross(w, u) / cross(v, w);
       return p.add(v.mul(t));
   }

   Point GetLineIntersection(Point p, Point v, Point q, Point w) {
       return GetLineIntersection(p, new Vector(v), q, new Vector(w));
   }

Polygon 多边形

类定义

class Polygon extends Vector {
    int num;
    Point[] v;

    Polygon() {
    }

    Polygon(int n) {
        num = n;
        v = new Point[num + 2];
}

关系判断

凸包判断

boolean IsConvexBag() {
        int direction = 0;// 1:counter-clockwise -1:clockwise
        for (int i = 0; i < num; i++) {
            int tmp = dcmp(cross(v[i], v[i + 1], v[i + 1], v[i + 2]));

            if (direction == 0) // prevent co-line
                direction = tmp;

            if (direction * tmp < 0) // as Vec is a ConvexBag,direction*temp>=0 no matter how direction rotates
                return false;
        }
        return true;
    }

Round 圆

类定义

class Round extends Vector {
    double r;
    Point o;

    Round(double _r, double _x, double _y) {
        r = _r;
        x = _x;
        y = _y;
        o = new Point(x, y);
    }

    double Area() {
        return pi * r * r;
    }
}

函数计算

求两圆面积交

double CommonArea(Round A, Round B) {
        double area = 0.0;
        Round M = dcmp(A.r - B.r) > 0 ? A : B;
        Round N = dcmp(A.r - B.r) > 0 ? B : A;
        double D = dist(M.o, N.o);
        if (dcmp(M.r + N.r - D) > 0 && dcmp(M.r - N.r - D) < 0) {
            double cosM = (M.r * M.r + D * D - N.r * N.r) / (2.0 * M.r * D);
            double cosN = (N.r * N.r + D * D - M.r * M.r) / (2.0 * N.r * D);
            double alpha = 2.0 * Math.acos(cosM);
            double beta = 2.0 * Math.acos(cosN);

            double TM = 0.5 * M.r * M.r * Math.sin(alpha);
            double TN = 0.5 * N.r * N.r * Math.sin(beta);
            double FM = 0.5 * alpha / pi * M.Area();
            double FN = 0.5 * beta / pi * N.Area();
            area = FM + FN - TM - TN;
        } else if (dcmp(M.r - N.r - D) >= 0) {
            area = N.Area();
        }
        return area;
}

求三角形与圆面积交

double TriAngleCircleInsection(Round C, Point A, Point B) {
        Vector OA = new Vector(A.sub(C.o)), OB = new Vector(B.sub(C.o));
        Vector BA = new Vector(A.sub(B)), BC = new Vector(C.o.sub(B));
        Vector AB = new Vector(B.sub(A)), AC = new Vector(C.o.sub(A));
        double DOA = OA.length(), DOB = OB.length(), DAB = AB.length(), r = C.r;
        if (dcmp(cross(OA, OB)) == 0)
            return 0;
        if (dcmp(DOA - C.r) < 0 && dcmp(DOB - C.r) < 0)
            return cross(OA, OB) * 0.5;
        else if (dcmp(DOB - r) < 0 && dcmp(DOA - r) >= 0) {
            double x = (dot(BA, BC) + Math.sqrt(r * r * DAB * DAB - cross(BA, BC) * cross(BA, BC))) / DAB;
            double TS = cross(OA, OB) * 0.5;
            return Math.asin(TS * (1 - x / DAB) * 2 / r / DOA) * r * r * 0.5 + TS * x / DAB;
        } else if (dcmp(DOB - r) >= 0 && dcmp(DOA - r) < 0) {
            double y = (dot(AB, AC) + Math.sqrt(r * r * DAB * DAB - cross(AB, AC) * cross(AB, AC))) / DAB;
            double TS = cross(OA, OB) * 0.5;
            return Math.asin(TS * (1 - y / DAB) * 2 / r / DOB) * r * r * 0.5 + TS * y / DAB;
        } else if (dcmp(Math.abs(cross(OA, OB)) - r * DAB) >= 0 || dcmp(dot(AB, AC)) <= 0 || dcmp(dot(BA, BC)) <= 0) {
            if (dcmp(dot(OA, OB)) < 0) {
                if (dcmp(cross(OA, OB)) < 0)
                    return (-Math.acos(-1.0) - Math.asin(cross(OA, OB) / DOA / DOB)) * r * r * 0.5;
                else
                    return (Math.acos(-1.0) - Math.asin(cross(OA, OB) / DOA / DOB)) * r * r * 0.5;
            } else
                return Math.asin(cross(OA, OB) / DOA / DOB) * r * r * 0.5;
        } else {
            double x = (dot(BA, BC) + Math.sqrt(r * r * DAB * DAB - cross(BA, BC) * cross(BA, BC))) / DAB;
            double y = (dot(AB, AC) + Math.sqrt(r * r * DAB * DAB - cross(AB, AC) * cross(AB, AC))) / DAB;
            double TS = cross(OA, OB) * 0.5;
            return (Math.asin(TS * (1 - x / DAB) * 2 / r / DOA) + Math.asin(TS * (1 - y / DAB) * 2 / r / DOB)) * r * r
                    * 0.5 + TS * ((x + y) / DAB - 1);
        }
}

Judge 关系判断

判断圆是否在多边形内部

boolean IsInPoly(Polygon pl) {
        double CircleAngle = 0.0; // rotation angle
        for (int i = 1; i <= pl.num; i++) // ignore the repetitive edges
            if (dcmp(cross(o, pl.v[i], o, pl.v[i + 1])) >= 0)
                CircleAngle += angle(o, pl.v[i], pl.v[i + 1]);
            else
                CircleAngle -= angle(o, pl.v[i], pl.v[i + 1]);

        if (dcmp(CircleAngle) == 0) // CircleAngle=0, Peg outside
            return false;
        else if (dcmp(CircleAngle - pi) == 0 || dcmp(CircleAngle + pi) == 0) // CircleAngle=180,
                                                                                // Peg inside(excluding vertices)
        {
            if (dcmp(r) == 0)
                return true;
        } else if (dcmp(CircleAngle - 2 * pi) == 0 || dcmp(CircleAngle + 2 * pi) == 0) // CircleAngle=360, Peg inside
            return true;
        else // CircleAngle in range (0,360)， Peg on the vertex
        {
            if (dcmp(r) == 0)
                return true;
        }
        return false;
    }

判断圆是否包含多边形


boolean IsFitPoly(Polygon pl) {
    for (int i = 0; i <= pl.num; i++) {
        int k = dcmp(Math.abs(cross(o, pl.v[i], o, pl.v[i + 1]) / dist(pl.v[i], pl.v[i + 1])) - r);
        if (k < 0)
            return false;
    }
    return true;
}

String 字符串篇

The Knuth-Morris-Pratt Algorithm KMP算法

class KMP {
    static int next[];

    static void getNext(String T) {
        next = new int[T.length() + 1];
        int j = 0, k = -1;
        next[0] = -1;
        while (j < T.length())
            if (k == -1 || T.charAt(j) == T.charAt(k))
                next[++j] = ++k;
            else
                k = next[k];
    }

    static int Index(String S, String T) {
        int i = 0, j = 0;
        getNext(T);

        for (i = 0; i < S.length() && j < T.length(); i++) {
            while (j > 0 && S.charAt(i) != T.charAt(j))
                j = next[j];
            if (S.charAt(i) == T.charAt(j))
                j++;
        }
        if (j == T.length())
            return i - T.length();
        else
            return -1;
    }

    static int Count(String S, String T) {
        int res = 0, j = 0;
        if (S.length() == 1 && T.length() == 1) {
            if (S.charAt(0) == T.charAt(0))
                return 1;
            else
                return 0;
        }
        getNext(T);
        for (int i = 0; i < S.length(); i++) {
            while (j > 0 && S.charAt(i) != T.charAt(j))
                j = next[j];
            if (S.charAt(i) == T.charAt(j))
                j++;
            if (j == T.length()) {
                res++;
                j = next[j];
            }
        }
        return res;
    }
}

Trie 字典树

存储仅含有小写英文字母的单词。
insert执行插入操作，query返回（存在该单词的前提下）某单词与其他任一单词的最长公共前缀长度。

class Trie {
	int cnt;
	Trie[] child;

	Trie() {
		child = new Trie[26];
		cnt = 0;
	}

	void insert(String s, int p) {
		int ch = s.charAt(p) - 'a';
		if (child[ch] == null)
			child[ch] = new Trie();
		child[ch].cnt++;
		if (p < s.length() - 1)
			child[ch].insert(s, p + 1);
	}

	int query(String s, int p) {
		int ch = s.charAt(p) - 'a';
		if (child[ch].cnt < 2 || p >= s.length() - 1)
			return p;
		return child[ch].query(s, p + 1);
	}
}

Aho-Corasick automaton AC自动机

class AC {
    final int maxl = 500010, maxc = 26;
    final char fstc = 'a';
    int root, L;
    int[][] next;
    int[] fail, end;
    Queue<Integer> que = new LinkedList<Integer>();

    AC() {
        next = new int[maxl][maxc];
        fail = new int[maxl];
        end = new int[maxl];
        L = 0;
        root = newnode();
    }

    void clear() {
        Arrays.fill(fail, 0);
        Arrays.fill(end, 0);
        L = 0;
        root = newnode();
    }

    int newnode() {
        Arrays.fill(next[L], -1);
        end[L++] = 0;
        return L - 1;
    }

    void insert(String str) {
        int now = root;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (next[now][ch - fstc] == -1)
                next[now][ch - fstc] = newnode();
            now = next[now][ch - fstc];
        }
        end[now]++;
    }

    void build() {
        que.clear();
        fail[root] = root;
        for (int i = 0; i < maxc; i++)
            if (next[root][i] == -1)
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.add(next[root][i]);
            }
        while (!que.isEmpty()) {
            int now = que.poll();
            for (int i = 0; i < maxc; i++)
                if (next[now][i] == -1)
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.add(next[now][i]);
                }
        }
    }

    int query(String str) {
        int now = root, res = 0;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            now = next[now][ch - fstc];
            int tmp = now;
            while (tmp != root) {
                res += end[tmp];
                // end[tmp] = 0;
                tmp = fail[tmp];
            }
        }
        return res;
    }
}

Network Flowing 网络流篇

Dinic 最大流/最小割

需应用数据结构弧、链式前向星并用以下函数代替addEdge（可能需改动参数）：

void addedge(int u, int v, int w) {
		e[num].modify(v, w, 0, h[u]);
		h[u] = num++;
		e[num].modify(u, w, 0, h[v]);
		h[v] = num++;
}

class Dinic {
	final int inf = 0x3fffffff;

	private int maxm, maxn;
	public Graph g;
	private int[] dist;
	private boolean[] vis;
	private Queue<Integer> que;

	public Dinic(int _n, int _m) {
		maxn = _n;
		maxm = _m;
		que = new LinkedList<Integer>();
		dist = new int[maxn];
		vis = new boolean[maxn];
	}

	void init() {
		if (g == null)
			g = new Graph(maxn, maxm);
		g.init();
	}

	void init(Graph _g) {
		g = _g;
	}

	void addEdge(int u, int v, int w) {
		g.addedge(u, v, w);
	}

	boolean bfs(int s, int t) {
		que.clear();
		Arrays.fill(dist, -1);
		Arrays.fill(vis, false);
		dist[s] = 0;
		que.add(s);
		vis[s] = true;
		while (!que.isEmpty()) {
			int u = que.poll();
			for (int i = g.h[u]; i != -1; i = g.e[i].next) {
				Edge E = g.e[i];
				if (!vis[E.to] && E.cap > E.flow) {
					dist[E.to] = dist[u] + 1;
					if (E.to == t)
						return true;
					vis[E.to] = true;
					que.add(E.to);
				}
			}
		}
		return false;
	}

	int dfs(int u, int delta, int target) {
		if (u == target || delta == 0)
			return delta;
		int flow = 0, f;
		for (int i = g.h[u]; i != -1; i = g.e[i].next) {
			Edge E = g.e[i];
			if (dist[E.to] == dist[u] + 1 && (f = dfs(E.to, Math.min(delta, E.cap - E.flow), target)) > 0) {
				g.e[i].flow += f;
				g.e[i ^ 1].flow -= f;
				flow += f;
				delta -= f;
				if (delta == 0)
					break;
			}
		}
		return flow;
	}

	int maxflow(int source, int target) {
		int flow = 0;
		while (bfs(source, target)) {
			flow += dfs(source, inf, target);
		}
		return flow;
	}
};

费用流

求解最小费用最大流。
若需要最大费用，可将各边费用取反，最终所得结果亦取反。
需应用数据结构有向边、链式前向星并用以下函数代替addEdge：

void addEdge(int u, int v, int f, int w) {
		e[num].modify(v, f, w, h[u]);
		h[u] = num++;
		e[num].modify(u, 0, -w, h[v]);
		h[v] = num++;
}

class MinCostMaxFlow {
	final int inf = 0x3fffffff;
	int maxn, maxm;
	Graph g;
	spfa work;
	int num, src, sink;

	public MinCostMaxFlow(int _n, int _m) {
		maxn = _n;
		maxm = _m;
		work = new spfa(maxn, maxm);
	}

	void init(int _u, int _v) {
		src = _u;
		sink = _v;
		if (g == null)
			g = new Graph(maxn, maxm);
		g.init();
	}

	void init(Graph _g, int _u, int _v) {
		src = _u;
		sink = _v;
		g = _g;
	}

	void addEdge(int u, int v, int f, int w) {
		g.addEdge(u, v, f, w);
	}

	boolean findPath() {
		work.init(g, src);
		return work.get_res(sink) < inf;
	}

	int solve() {
		int cost = 0, flow = 0;
		while (findPath()) {
			int u = sink;
			int delta = inf;
			while (u != src) {
				delta = Math.min(delta, g.e[work.pree[u]].f);
				u = work.prev[u];
			}
			u = sink;
			while (u != src) {
				g.e[work.pree[u]].f -= delta;
				g.e[work.pree[u] ^ 1].f += delta;
				u = work.prev[u];
			}
			cost += work.dis[sink] * delta;
			flow += delta;
		}
		return cost;
	}
}

差分约束

差分约束系统（system of difference constraints），是求解关于一组变数的特殊不等式组之方法。
如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如$ x_j-x_i \le b_k(i,j∈[1,n],k∈[1,m]) $,则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
求解差分约束系统，可以转化成图论的单源最短路径问题。观察$ x_j-x_i \le b_k $，会发现它类似最短路中的三角不等式$ d[v] \le d[u]+w[u,v] $，即$ d[v]-d[u] \le w[u,v] $。因此，以每个变数$ x_i $为结点，对于约束条件$ x_j-x_i \le b_k $，连接一条边(i,j)，边权为$ b_k $。再增加一个原点(s,s)与所有定点相连，边权均为0。对这个图以s为原点运行Bellman-ford算法（或SPFA算法），最终{d[i]}即为一组可行解。

ACM竞赛Java模板[dev-160504]

https://devblog.citruxonve.net/posts/41b311d1/

Author

Semprathlon / Simfae Dean

Posted on

04/06/2016

Updated on

07/19/2023

Licensed under

#Template Java

ACM竞赛Java模板[dev-160504]

Java Code Template By Semprathlon

Input 输入

Output 输出

Data Structure 数据结构篇

Pair 二元组

Queue 队列

Priority Queue 优先队列

Heap 堆

Directional edge 有向边

Arc 弧

Adjacent Table 链式前向星（邻接表）

ST table ST表

Segment Tree 线段树

Binary Indexed Tree 树状数组

Graph Theory 图论篇

Topological Sorting 拓扑排序

Hungarian Algorithm 二分图最大匹配 - 匈牙利算法

Hopcroft-Karp Algorithm 二分图最大匹配 - HK算法

SPFA最短路径

Number Theory 数论篇

Extended Euclid Theorem 扩展欧几里得定理

Modular multiplicative inverse 模逆元

Quick power and modulo 快速幂取模

Multiply and modulo 乘法取模

Division and modulo 除法取模

Factorial and modulo 阶乘取模

Prime filtering (linear) 线性筛质数

Calculating Euler function $ φ(n) $ 求欧拉函数值

Calculating Möbius function $ μ(n) $ 求莫比乌斯函数值

Integer Prime Factorization 分解质因数

Quick Greatest Common Divisor 快速求最大公约数

Chinese Remainer Theorem 中国剩余定理

Combinatorial Mathematics 组合数学篇

Combination Calculation #1 组合数计算1

Combination Calculation #2 组合数计算2

Lucas Theorem 卢卡斯定理

Catalan number 卡塔兰数

Stirling numbers of the 1st kind 第一类斯特灵数

Stirling numbers of the 2nd kind 第二类斯特灵数

Double Comparing 实数的比较

Degree/Radian 角度/弧度互化

Point 点

类定义

函数计算

Vector 向量

类定义

基本运算

函数计算

Line 直线/线段

类定义

关系判断

函数计算

Polygon 多边形

类定义

关系判断

Round 圆

类定义

函数计算

Judge 关系判断

String 字符串篇

The Knuth-Morris-Pratt Algorithm KMP算法

Trie 字典树

Aho-Corasick automaton AC自动机

Network Flowing 网络流篇

Dinic 最大流/最小割

费用流

差分约束

Author

Posted on

Updated on

Licensed under

Comments

Categories

Tags

Subscribe for updates

Links