【这次市选我挂得很惨……前3题全部爆0(骗分都米骗到)……就这种烂成绩还能进市队,可见合肥人之沙茶……】
最不该挂的是第一题。第一问就是个裸的最大闭合子图,关键就出在第二问上,要求最大闭合子图的最小容量。本沙茶后来才发现这竟然是PKU原题!(PKU2987),因为,最大流求出来的最大闭合子图一定是容量最小的!故第二问只要在求出最大流后来一次遍历,找到S可达的结点个数即可。

详细证明(转网上某神犇的):
———————————————————————————————————————————————————最大权不可能是负数,当是0的情况,自然是一个点不选最优,下面探讨忽略0的情况。

         1:首先我假设有两个闭合子图都拥有相同的最大权,并且没有共同点,很容易证明不会出现这种情况,因为如果我们把两个闭合子图都选择上,那么最大权会变大。

         2:仍然假设有两个闭合子图都拥有相同的最大权,但是有共同点,即重叠的意思。根据闭合图的特点,这些共同点不是随意的,可以知道,只要有一个点相同,那么这个点的能到达的所有后续点都必定是共同点。所以会得出一个结论,两个闭合子图重叠,重叠的部分必然是1个或者多个不重叠闭合图。


    然后我们考虑不重叠的部分,这部分的点权和可以证明一定是非负。我们可以假设非重叠部分的点权和是负数,那么假如我们删掉这部分,只选取重叠部分(因为重叠部分肯定是闭合图),那么最大权也会变大,矛盾。所以非重叠部分点权和一定是非负数。
    下面继续探讨非重叠部分的性质。上面的证明已经得出他们的点权和一定是非负。下面先抛开点权和等于0的情况,先讨论正数的情况。
假设两个闭合子图的非重叠部分都是正数,那么把这两个部分加起来重新构成闭合图,最大权必然会变大,与假设的两个同为最大权的闭合图矛盾。固可以证明非重叠部分的点权和肯定是0。

    探讨到这部分,我们已经可以初步得出一个结论,就是一个最大权闭合子图的点数多少问题只能受到一些0权和子图(所有点权加起来等于0的子图)的干扰。

    重点来到这些0权和子图上。下面我们又来做一个假设,就是假设我们求出了一个最大权闭合子图,并且里面有包含到一些0权和子图。而我们这时候需要做的就是找到那些可以删去的0权和子图,当我们删去了所有的这些子图,那么点数就可以达到最小。

    关键来了。到底哪些0权和子图是可以删去的,哪些0权和子图是不可以删去的呢?

    根据闭合图的性质,我们要删除一个点,那么必须把所有能到达这个点的点删去。那么很清晰的看到要删除一个子图,必须保证在这个子图外没有任何一个点指向这个子图。也就是说这个子图是封闭的,只有出边,没有入边。



    最后一步,假如我们能证明在求解最大权闭合图的过程中保证不会选上这些0权和子图,那么这个证明就可以结束了。
通过最大流求解最大权闭合子图,我们把正点权和源点建边,边权为点权值,负点权和汇点建边,边权为点权绝对值。仔细分析求解最大流的过程,会发现一些东西。

    由于那些可选可不选的0权和子图是封闭的,没有入边的,那么在求解最大流的过程中,不可能有外部流补充,所以这些0权和子图的每个点与源或者汇的边都是满流的。





    最后求最大权闭合子图的点,方法是从源点开始通过非满流边搜索一个联通图,图内的点(除了源点)就是求出来的最大权闭合子图的点。而上面证明到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 = 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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理