算法合集之淺析最大最小定理在信息學競賽中的應用(參考版)
2024-10-19 20:32本頁面
【正文】 根據(jù)上式和 ci*j*=uij可得 ?對于任意的 (i,j)∈ Q，都有 xij=uij。那么 Q中的所有邊對應到 G*就形成了一個環(huán)，稱為 W*。 最大 — 最小定理 ?共同點 ?考察的兩個最優(yōu)化問題互為對偶問題 ?證明的過程 ?最大化問題 M的任何一個解 m的值都不超過最小化問題 N的任何一個解 n的值 ?可以找到 M的一個解 p和 N的一個解 q，且它們的值相等 ?p和 q分別為各自問題的一個最優(yōu)解 ?簡潔的最優(yōu)性證明 總結 K246。nig定理 ?應用 ?二部圖最小覆蓋和最大匹配的 互相轉化 ?[例一 ] Muddy Fields 最大流 — 最小割定理 ? 近年來 ， 網(wǎng)絡流尤其是最大流問題越來越多的出現(xiàn)在各類信息學競賽當中 ? 最大流 — 最小割定理是整個最大流問題的基礎與核心 ， 其主要內容是： 1. 最大流的流量不超過最小割的容量 2. 存在一個流 x和一個割 c， 且 x的流量等于 c的容量 [例二 ] Moving the Hay ?一個牧場由 R*C個格子組成 ?牧場內有 N條干草運輸通道，每條連接兩個水平或垂直相鄰的方格，最大運輸量為 Li ?(1,1)內有很多干草， Farmer John希望將最多的干草運送到 (R,C)內 ?求最大運輸量 [例二 ] Moving the Hay ?一個 R=C=3的例子，最大運輸量為 7 ?數(shù)據(jù)規(guī)模： R,C ≤ 200 (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,2) (3,3) 5,5 3,2 5,5 2,2 1,1 6,6 4,1 7,6 (3,1) 分析 ?直接求最大流 ?以每個方格為點，每條通道為邊，邊的容量就是它的最大運輸量 ?從 (1,1)到 (R,C)的最大運輸量就是將這兩個方格對應的點分別作為流網(wǎng)絡中的源和匯求出的最大流量 ?效率？？？ ?點數(shù)最大 40000，邊數(shù)最大 80000！ 分析 ?效率低下的原因 ?沒有利用題目的特點，直接套用經(jīng)典算法 ?特點 ?題目中給出的是一個平面圖 ?圖中的一個點為源點 s，另外一個點為匯點 t，且 s和 t都在圖中的無界面的邊界上 分析 4 5 2 3 1 6 f1 f2 f3 f4 分析 ?效率低下的原因 ?沒有利用題目的特點，直接套用經(jīng)典算法 ?特點 ?題目中給出的是一個平面圖 ?圖中的一個點為源點 s，另
教學課件相關推薦
鄂ICP備17016276號-1