\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{interval}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\geometry{left=2.5cm,right=2.5cm,headsep=1cm,bottom=2cm,footnotesep=2cm,headheight=13pt}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{\ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年5月19日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{automata, positioning, arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题1.\arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\lstset{basicstyle=\ttfamily}

\begin{document}

\section*{整数规划}

最短路径可以转化为线性规划问题

除了一种比较简单的方法：

求\[\max d_t\]服从\[d_v\leqslant d_u+w(u,v)\forall (u,v)\in E\]且\[d_s=0\]

还可以考虑一种整数规划的方式：

定义$X_e\in\{0, 1\}$，分别对应是否被取出，则有
\[
    \begin{cases}
        \sum_{v\in N(s)}X_{(s,v)}=1                        \\
        \sum_{v\in N(t)}X_{(v,t)}=1                        \\
        \forall v\in V-\{s,t\},\sum_{u\in N(v)}X_{(u,v)}=2 \\
        \forall e\in E,X_e\in\{0,1\}
    \end{cases}
\]

类似地，也可以考虑最大匹配，即求\[\max\sum_{(u,v)\in E}X_{(u,v)}\]满足
\[
    \begin{cases}
        \forall v\in V,\sum_{u\in N(v)}X_{(u,v)}\leqslant 1 \\
        \forall e\in E,X_e\in\{0,1\}
    \end{cases}
\]

\section*{线性规划解决最大流问题}

如果两点无边，则加上一条容量为0的平衡边，这样就可以当作完全图求解.

求\[\max[\sum_{v\in V}f_{sv}-\sum_v\in V]f_{vs}\]服从
\[
    \begin{cases}
        f_{uv}\leqslant c(u,v)                                               \\
        \forall v\in V-\{s,t\},\sum_{u\in N(v)}f_{uv}=\sum_{u\in N(v)}f_{vu} \\
        \forall v\in V,f_{sv}-\sum_{u\in N(v)}f_{uv}=0                       \\
        \forall v\in V,f_{vt}-\sum_{u\in N(v)}f_{vu}=0                       \\
        \forall e\in E,f_e\geqslant 0
    \end{cases}
\]

\section*{最小费用流}

有向图，容量$c(u,v)\geqslant0$，费用$a(u,v)$，源点流出量固定为$d$，求总费用最小.

求\[\min\sum_{(u,v)\in E}a(u,v)f_{uv}\]服从
\[
    \begin{cases}
        \forall u,v\in V,f_{uv}\leqslant c(u,v)                              \\
        \forall v\in V-\{s,t\},\sum_{u\in N(v)}f_{uv}=\sum_{u\in N(v)}f_{vu} \\
        \forall v\in V,f_{sv}-\sum_{u\in N(v)}f_{uv}=d                       \\
        \forall e\in E,f_e\geqslant 0
    \end{cases}
\]

\section*{最小割}

线性规划的对偶性

\end{document}