• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            【這次市選我掛得很慘……前3題全部爆0(騙分都米騙到)……就這種爛成績(jī)還能進(jìn)市隊(duì),可見合肥人之沙茶……】
            最不該掛的是第一題。第一問就是個(gè)裸的最大閉合子圖,關(guān)鍵就出在第二問上,要求最大閉合子圖的最小容量。本沙茶后來才發(fā)現(xiàn)這竟然是PKU原題!(PKU2987),因?yàn)椋畲罅髑蟪鰜淼淖畲箝]合子圖一定是容量最小的!故第二問只要在求出最大流后來一次遍歷,找到S可達(dá)的結(jié)點(diǎn)個(gè)數(shù)即可。

            詳細(xì)證明(轉(zhuǎn)網(wǎng)上某神犇的):
            ———————————————————————————————————————————————————最大權(quán)不可能是負(fù)數(shù),當(dāng)是0的情況,自然是一個(gè)點(diǎn)不選最優(yōu),下面探討忽略0的情況。

                     1:首先我假設(shè)有兩個(gè)閉合子圖都擁有相同的最大權(quán),并且沒有共同點(diǎn),很容易證明不會(huì)出現(xiàn)這種情況,因?yàn)槿绻覀儼褍蓚€(gè)閉合子圖都選擇上,那么最大權(quán)會(huì)變大。

                     2:仍然假設(shè)有兩個(gè)閉合子圖都擁有相同的最大權(quán),但是有共同點(diǎn),即重疊的意思。根據(jù)閉合圖的特點(diǎn),這些共同點(diǎn)不是隨意的,可以知道,只要有一個(gè)點(diǎn)相同,那么這個(gè)點(diǎn)的能到達(dá)的所有后續(xù)點(diǎn)都必定是共同點(diǎn)。所以會(huì)得出一個(gè)結(jié)論,兩個(gè)閉合子圖重疊,重疊的部分必然是1個(gè)或者多個(gè)不重疊閉合圖。


                然后我們考慮不重疊的部分,這部分的點(diǎn)權(quán)和可以證明一定是非負(fù)。我們可以假設(shè)非重疊部分的點(diǎn)權(quán)和是負(fù)數(shù),那么假如我們刪掉這部分,只選取重疊部分(因?yàn)橹丿B部分肯定是閉合圖),那么最大權(quán)也會(huì)變大,矛盾。所以非重疊部分點(diǎn)權(quán)和一定是非負(fù)數(shù)。
                下面繼續(xù)探討非重疊部分的性質(zhì)。上面的證明已經(jīng)得出他們的點(diǎn)權(quán)和一定是非負(fù)。下面先拋開點(diǎn)權(quán)和等于0的情況,先討論正數(shù)的情況。
            假設(shè)兩個(gè)閉合子圖的非重疊部分都是正數(shù),那么把這兩個(gè)部分加起來重新構(gòu)成閉合圖,最大權(quán)必然會(huì)變大,與假設(shè)的兩個(gè)同為最大權(quán)的閉合圖矛盾。固可以證明非重疊部分的點(diǎn)權(quán)和肯定是0。

                探討到這部分,我們已經(jīng)可以初步得出一個(gè)結(jié)論,就是一個(gè)最大權(quán)閉合子圖的點(diǎn)數(shù)多少問題只能受到一些0權(quán)和子圖(所有點(diǎn)權(quán)加起來等于0的子圖)的干擾。

                重點(diǎn)來到這些0權(quán)和子圖上。下面我們又來做一個(gè)假設(shè),就是假設(shè)我們求出了一個(gè)最大權(quán)閉合子圖,并且里面有包含到一些0權(quán)和子圖。而我們這時(shí)候需要做的就是找到那些可以刪去的0權(quán)和子圖,當(dāng)我們刪去了所有的這些子圖,那么點(diǎn)數(shù)就可以達(dá)到最小。

                關(guān)鍵來了。到底哪些0權(quán)和子圖是可以刪去的,哪些0權(quán)和子圖是不可以刪去的呢?

                根據(jù)閉合圖的性質(zhì),我們要?jiǎng)h除一個(gè)點(diǎn),那么必須把所有能到達(dá)這個(gè)點(diǎn)的點(diǎn)刪去。那么很清晰的看到要?jiǎng)h除一個(gè)子圖,必須保證在這個(gè)子圖外沒有任何一個(gè)點(diǎn)指向這個(gè)子圖。也就是說這個(gè)子圖是封閉的,只有出邊,沒有入邊。



                最后一步,假如我們能證明在求解最大權(quán)閉合圖的過程中保證不會(huì)選上這些0權(quán)和子圖,那么這個(gè)證明就可以結(jié)束了。
            通過最大流求解最大權(quán)閉合子圖,我們把正點(diǎn)權(quán)和源點(diǎn)建邊,邊權(quán)為點(diǎn)權(quán)值,負(fù)點(diǎn)權(quán)和匯點(diǎn)建邊,邊權(quán)為點(diǎn)權(quán)絕對(duì)值。仔細(xì)分析求解最大流的過程,會(huì)發(fā)現(xiàn)一些東西。

                由于那些可選可不選的0權(quán)和子圖是封閉的,沒有入邊的,那么在求解最大流的過程中,不可能有外部流補(bǔ)充,所以這些0權(quán)和子圖的每個(gè)點(diǎn)與源或者匯的邊都是滿流的。





                最后求最大權(quán)閉合子圖的點(diǎn),方法是從源點(diǎn)開始通過非滿流邊搜索一個(gè)聯(lián)通圖,圖內(nèi)的點(diǎn)(除了源點(diǎn))就是求出來的最大權(quán)閉合子圖的點(diǎn)。而上面證明到0權(quán)和子圖的點(diǎn)和源匯都是滿流,并且沒有入邊,出邊也沒有流,那么肯定無法從源點(diǎn)搜索到。那么在求解的過程中這些0權(quán)和子圖的點(diǎn)是肯定沒有選上的。

               就此證畢。
               結(jié)論:通過最大流求解最大權(quán)閉合子圖的問題,求出來的閉合子圖點(diǎn)數(shù)也是最少的。

            ———————————————————————————————————————————————————
            代碼:
            #include <iostream>
            #include 
            <stdio.h>
            #include 
            <string.h>
            using namespace std;
            #define re(i, n) for (int i=0; i<n; i++)
            #define re1(i, n) for (int i=1; i<=n; i++)
            const int MAXN = 10002, MAXM = 120000, INF = ~0U >> 2;
            struct edge {
                
            int a, b, f, next;
                edge () {}
                edge (
            int _a, int _b, int _f) : a(_a), b(_b), f(_f), next(-1) {}
            } ed[MAXM 
            + MAXM];
            int n, m = 0, s, t, hd[MAXN], tl[MAXN], st[MAXN], lev[MAXN], pr[MAXN], hs[MAXN], q[MAXN], now, res = 0, res_num = 0;
            bool vst[MAXN];
            void add_edge(int a, int b, int f)
            {
                ed[m] 
            = edge(a, b, f);
                
            if (hd[a] != -1) tl[a] = ed[tl[a]].next = m++else hd[a] = tl[a] = m++;
                ed[m] 
            = edge(b, a, 0);
                
            if (hd[b] != -1) tl[b] = ed[tl[b]].next = m++else hd[b] = tl[b] = m++;
            }
            void init()
            {
                freopen(
            "profit.in""r", stdin);
                
            int n0, m0, a0, b0, x;
                scanf(
            "%d%d"&n0, &m0);
                n 
            = n0 + 2; s = 0; t = n - 1;
                memset(hd, 
            -1, n << 2); memset(tl, -1, n << 2);
                re1(i, n0) {
                    cin 
            >> x;
                    
            if (x > 0) {add_edge(s, i, x); res += x;}
                    
            if (x < 0) add_edge(i, t, -x);
                }
                re1(i, m0) {
                    scanf(
            "%d%d"&a0, &b0);
                    add_edge(a0, b0, INF);
                }
                fclose(stdin);
            }
            void aug()
            {
                
            int z = hs[t], i = t, p;
                
            while (i != s) {
                    hs[i] 
            -= z; p = pr[i]; ed[p].f -= z; ed[p ^ 1].f += z; i = ed[p].a;
                    
            if (!ed[p].f) now = i;
                }
                res 
            -= z;
            }
            bool dfs()
            {
                q[
            0= s; memset(vst, 0, n); vst[s] = 1; lev[s] = 0;
                
            int i, j, f0;
                
            for (int front=0, rear=0; front<=rear; front++) {
                    i 
            = q[front];
                    
            for (int p=hd[i]; p != -1; p=ed[p].next) {
                        j 
            = ed[p].b; f0 = ed[p].f;
                        
            if (!vst[j] && f0) {vst[j] = 1; lev[j] = lev[i] + 1; q[++rear] = j;}
                    }
                }
                
            if (!vst[t]) return 0;
                now 
            = s; memset(vst, 0, n); hs[s] = INF;
                re(i, n) st[i] 
            = hd[i];
                
            bool ff;
                
            while (!vst[s]) {
                    
            if (now == t) aug();
                    ff 
            = 0;
                    
            for (int p=st[now]; p != -1; p=ed[p].next) {
                        j 
            = ed[p].b; f0 = ed[p].f;
                        
            if (lev[now] + 1 == lev[j] && !vst[j] && f0) {st[now] = pr[j] = p; hs[j] = hs[now] <= f0 ? hs[now] : f0; now = j; ff = 1break;}
                    }
                    
            if (!ff) {
                        vst[now] 
            = 1;
                        
            if (now != s) now = ed[pr[now]].a;
                    }
                }
                
            return 1;
            }
            void solve()
            {
                
            while (dfs()) ;
                q[
            0= s; memset(vst, 0, n); vst[s] = 1;
                
            int i, j, f0;
                
            for (int front=0, rear=0; front<=rear; front++) {
                    i 
            = q[front];
                    
            for (int p=hd[i]; p != -1; p=ed[p].next) {
                        j 
            = ed[p].b; f0 = ed[p].f;
                        
            if (!vst[j] && f0) {vst[j] = 1; res_num++; q[++rear] = j;}
                    }
                }
            }
            void pri()
            {
                freopen(
            "profit.out""w", stdout);
                printf(
            "%d\n%d\n", res, res_num);
                fclose(stdout);
            }
            int main()
            {
                init();
                solve();
                pri();
                
            return 0;
            }

            午夜天堂精品久久久久| 香蕉久久夜色精品国产小说| 午夜不卡久久精品无码免费| 国产婷婷成人久久Av免费高清 | 午夜不卡久久精品无码免费| 久久精品国产精品青草app| 欧美一级久久久久久久大片| 久久天天躁狠狠躁夜夜2020一 | 亚洲国产成人久久综合野外| 婷婷伊人久久大香线蕉AV| 国产日韩久久久精品影院首页 | 久久成人国产精品二三区| 亚洲欧美成人久久综合中文网 | 久久精品极品盛宴观看| 久久er国产精品免费观看2| 久久天天躁狠狠躁夜夜躁2014| 91精品国产综合久久香蕉 | 久久www免费人成看国产片| 精品久久久久久成人AV| 亚洲人AV永久一区二区三区久久 | 久久精品国产只有精品66 | 久久美女人爽女人爽| 久久精品亚洲中文字幕无码麻豆| 色偷偷88欧美精品久久久| 狠狠色婷婷综合天天久久丁香| 成人午夜精品无码区久久| 天天做夜夜做久久做狠狠| 久久久WWW成人免费精品| 美女写真久久影院| 久久精品国内一区二区三区| 久久婷婷五月综合国产尤物app| 久久综合久久伊人| 久久精品国产精品亜洲毛片| 97精品国产97久久久久久免费 | 超级97碰碰碰碰久久久久最新| 九九久久精品无码专区| 久久国产综合精品五月天| 曰曰摸天天摸人人看久久久| 99久久精品国产麻豆| 久久99国产精品久久| av午夜福利一片免费看久久|