【這次市選我掛得很慘……前3題全部爆0（騙分都米騙到）……就這種爛成績還能進市隊，可見合肥人之沙茶……】
最不該掛的是第一題。第一問就是個裸的最大閉合子圖，關鍵就出在第二問上，要求最大閉合子圖的最小容量。本沙茶后來才發(fā)現(xiàn)這竟然是PKU原題?。≒KU2987），因為，最大流求出來的最大閉合子圖一定是容量最小的！故第二問只要在求出最大流后來一次遍歷，找到S可達的結點個數即可。
詳細證明（轉網上某神犇的）：
———————————————————————————————————————————————————
最大權不可能是負數，當是0的情況，自然是一個點不選最優(yōu)，下面探討忽略0的情況。
1：首先我假設有兩個閉合子圖都擁有相同的最大權，并且沒有共同點，很容易證明不會出現(xiàn)這種情況，因為如果我們把兩個閉合子圖都選擇上，那么最大權會變大。
2：仍然假設有兩個閉合子圖都擁有相同的最大權，但是有共同點，即重疊的意思。根據閉合圖的特點，這些共同點不是隨意的，可以知道，只要有一個點相同，那么這個點的能到達的所有后續(xù)點都必定是共同點。所以會得出一個結論，兩個閉合子圖重疊，重疊的部分必然是1個或者多個不重疊閉合圖。
然后我們考慮不重疊的部分，這部分的點權和可以證明一定是非負。我們可以假設非重疊部分的點權和是負數，那么假如我們刪掉這部分，只選取重疊部分（因為重疊部分肯定是閉合圖），那么最大權也會變大，矛盾。所以非重疊部分點權和一定是非負數。
下面繼續(xù)探討非重疊部分的性質。上面的證明已經得出他們的點權和一定是非負。下面先拋開點權和等于0的情況，先討論正數的情況。
假設兩個閉合子圖的非重疊部分都是正數，那么把這兩個部分加起來重新構成閉合圖，最大權必然會變大，與假設的兩個同為最大權的閉合圖矛盾。固可以證明非重疊部分的點權和肯定是0。
探討到這部分，我們已經可以初步得出一個結論，就是一個最大權閉合子圖的點數多少問題只能受到一些0權和子圖（所有點權加起來等于0的子圖）的干擾。
重點來到這些0權和子圖上。下面我們又來做一個假設，就是假設我們求出了一個最大權閉合子圖，并且里面有包含到一些0權和子圖。而我們這時候需要做的就是找到那些可以刪去的0權和子圖，當我們刪去了所有的這些子圖，那么點數就可以達到最小。
關鍵來了。到底哪些0權和子圖是可以刪去的，哪些0權和子圖是不可以刪去的呢？
根據閉合圖的性質，我們要刪除一個點，那么必須把所有能到達這個點的點刪去。那么很清晰的看到要刪除一個子圖，必須保證在這個子圖外沒有任何一個點指向這個子圖。也就是說這個子圖是封閉的，只有出邊，沒有入邊。
最后一步，假如我們能證明在求解最大權閉合圖的過程中保證不會選上這些0權和子圖，那么這個證明就可以結束了。
通過最大流求解最大權閉合子圖，我們把正點權和源點建邊，邊權為點權值，負點權和匯點建邊，邊權為點權絕對值。仔細分析求解最大流的過程，會發(fā)現(xiàn)一些東西。
由于那些可選可不選的0權和子圖是封閉的，沒有入邊的，那么在求解最大流的過程中，不可能有外部流補充，所以這些0權和子圖的每個點與源或者匯的邊都是滿流的。
最后求最大權閉合子圖的點，方法是從源點開始通過非滿流邊搜索一個聯(lián)通圖，圖內的點（除了源點）就是求出來的最大權閉合子圖的點。而上面證明到0權和子圖的點和源匯都是滿流，并且沒有入邊，出邊也沒有流，那么肯定無法從源點搜索到。那么在求解的過程中這些0權和子圖的點是肯定沒有選上的。
就此證畢。
結論：通過最大流求解最大權閉合子圖的問題，求出來的閉合子圖點數也是最少的。
———————————————————————————————————————————————————
代碼：
#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 = 1; break;}
}
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;
}