\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[hidelinks]{hyperref}
\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}

\setlength{\headheight}{0pt}
\geometry{left=2.5cm,right=2.5cm,headsep=2cm,bottom=2cm,footnotesep=2cm}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{
    \begin{huge}
        \textbf{}
    \end{huge}\\
    \vspace{0.4cm}
    \ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年12月22日}

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

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

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{arrows, positioning}

\newcounter{aufgc}
\newenvironment{exercise}[1]%
{\refstepcounter{aufgc}\textbf{问题 \arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

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

\definecolor{mygray}{rgb}{0.4,0.4,0.4}
\definecolor{mygreen}{rgb}{0,0.8,0.6}
\definecolor{myorange}{rgb}{1.0,0.4,0}

\lstset{
    basicstyle=\footnotesize\sffamily\color{black},
    basicstyle=\tt,
    keywordstyle=\color{purple}\bfseries,
    commentstyle=\color{mygray},
    numbers=left,
    numbersep=5pt,
    numberstyle=\tiny\color{mygray},
    showspaces=false,
    showstringspaces=false,
    stringstyle=\color{myorange},
    tabsize=2,
    backgroundcolor=\color[RGB]{245,245,244}
}

\def\drawell#1#2#3#4{
    \draw[draw=black, fill=gray, fill opacity=#4] (0,#1) circle [x radius=#2, y radius=#3];
}

\begin{document}

\textbf{Q1.}

\begin{figure}[h]
    \centering
    \begin{minipage}[t]{0.48\textwidth}
        \centering
        \begin{tikzpicture}
            \drawell{0}{2}{2}{0};
            \drawell{-1.25}{1.3}{0.75}{.1};
            \drawell{2}{2}{1.8}{.2};
            \node at (0, 3) {{\bf NP-hard}};
            \node at (0, 1.2) {{\bf NP-Complete}};
            \node at (0, -0.2) {{\bf NP}};
            \node at (0,-1.5) {{\bf P}};
            \node at (0,-2.5) {$\bf P\neq NP$};
        \end{tikzpicture}
    \end{minipage}
    \begin{minipage}[t]{0.48\textwidth}
        \centering
        \begin{tikzpicture}
            \drawell{0}{2}{2}{.1};
            \drawell{2}{3}{4}{0};
            \node at (0, 3) {{\bf NP-hard}};
            \node at (0, 0) {\bf P=NP=NP-Complete};
            \node at (0,-2.5) {$\bf P=NP$};
        \end{tikzpicture}
    \end{minipage}
\end{figure}

\hrulefill\medskip

\textbf{Q2.}

\begin{figure}[h]
    \centering
    \begin{tikzpicture}
        \node[draw, circle] (1) {1};
        \node[draw, circle] (2) [above=of 1] {2};
        \node[draw, circle] (3) [above left=of 1, yshift=-0.5cm] {3};
        \node[draw, circle] (4) [below left=of 1, yshift=0.5cm] {4};
        \node[draw, circle] (5) [below=of 1] {5};
        \node[draw, circle] (6) [below right=of 1, yshift=0.5cm] {6};
        \node[draw, circle] (7) [above right=of 1, yshift=-0.5cm] {7};

        \draw (1) edge node {} (7)
        edge node {} (6)
        edge node {} (5)
        edge node {} (4)
        edge node {} (3)
        edge node {} (2);

    \end{tikzpicture}
\end{figure}

如图，不论随机选的哪条边，都会选到顶点 1 和另一个顶点，选取的顶点子集
大小为 2，而实际最优解为只需选取顶点 1，因而总是产生次优解。

\hrulefill\medskip

\textbf{Q3.}

首先判断 $T$ 和 $T'$ 长度是否相同，然后只需将 $T'$ 和自己拼接，
用 $T$ 作为模式串在 $T'T'$ (表示 $T'$ 自己和自己拼接)中匹配，
如果可以匹配，则说明 $T'$ 是 $T$ 的循环旋转。因为使用 KMP 算法
匹配是线性复杂度，所以这个算法是线性的。

\newpage

\textbf{Q4.}

(a)

\begin{figure}[h]
    \centering
    \begin{tikzpicture}[->,>=stealth]
        \node[draw, circle] (1) at (0,0) {$s$};
        \node[draw, circle] (2) at (1.4,1.4) {$a$};
        \node[draw, circle] (3) at (1.4,-1.4) {$b$};
        \node[draw, circle] (4) at (3.4,1.4) {$c$};
        \node[draw, circle] (5) at (3.4,-1.4) {$d$};
        \node[draw, circle] (6) at (4.8,0) {$t$};
        \draw[->] (1) edge [transform canvas={xshift=-1pt,yshift=1pt}, above] node{5}(2)
        edge [transform canvas={xshift=1pt,yshift=1pt}, above] node{1} (3)
        (2) edge [transform canvas={xshift=1pt,yshift=-1pt},below] node{4} (1)
        edge [transform canvas={xshift=1pt},right] node{3} (3)
        (3) edge [transform canvas={xshift=-1pt,yshift=-1pt},below] node{8} (1)
        edge [transform canvas={xshift=-1pt},left] node{5} (2)
        edge [transform canvas={xshift=-1pt,yshift=1pt},above] node{2} (4)
        edge [transform canvas={yshift=1pt},above] node{3} (5)
        (4) edge [above] node {7} (2)
        edge [transform canvas={xshift=1pt,yshift=-1pt},below] node{3} (3)
        (5) edge [transform canvas={yshift=-1pt},below] node{7} (3)
        edge [right] node {6} (4)
        edge [transform canvas={xshift=1pt,yshift=-1pt},below] node{5}(6)
        (6) edge [above] node{5} (4)
        edge [transform canvas={xshift=-1pt,yshift=1pt},above] node{7} (5);
    \end{tikzpicture}
\end{figure}

(b) 最大增广路为 $s,a,b,d,t$，流量提升为 3

(c)

\begin{figure}[h]
    \centering
    \begin{tikzpicture}[->,>=stealth]
        \node[draw, circle] (1) at (0,0) {$s$};
        \node[draw, circle] (2) at (1.4,1.4) {$a$};
        \node[draw, circle] (3) at (1.4,-1.4) {$b$};
        \node[draw, circle] (4) at (3.4,1.4) {$c$};
        \node[draw, circle] (5) at (3.4,-1.4) {$d$};
        \node[draw, circle] (6) at (4.8,0) {$t$};
        \draw[->] (1) edge node{7/7}(2)
        edge node{8/9} (3)
        (2) edge node{7/7} (4)
        (3) edge node{0/8} (2)
        edge node{10/10} (5)
        (4) edge node{2/5} (3)
        edge node {5/5} (6)
        (5) edge node {0/6} (4)
        edge node{10/12}(6);
    \end{tikzpicture}
\end{figure}

\hrulefill\medskip

\textbf{附加题}

收获上还是很多的，学习了很多算法基础思想，比如分治、贪心、动态规划等等，
不过建议以后可以考虑尽早开始布置作业和实验，不然像今年就到了十六周还有作业。

\end{document}