最大闭合子图的预处理(去环)问题

Posted on 2011-03-27 18:30 Mato_No1 阅读(1477) 评论(3)  编辑 收藏 引用 所属分类: 网络流图算法
网络流最让人不能忍受的不是模板,而是建模!尤其是某些题目里面需要搞一段很长的预处理才能开始写网络流……

最大闭合子图就是其中的一种。如果要求最大闭合子图的有向图里面有环就很囧了,因为在某些题目里(比如NOI2009的pvz),取点是有先后顺序的,因此环中的点一个也取不了(有的题则不是这样,子图里的点可以一次全部取来,这时对于环就有两种方案了:要么全取,要么一个不取,此时不用管环,直接进入网络流即可),不仅如此,根据闭合子图的定义,如果一个点i可以到达一个点j(注,是“可以到达”点j,也就是从i到j有路径),而点j属于某个环,那么点i也不能取,因此在预处理中需要把点i也删掉。以下将属于某个环中的点成为“环点”,将可以到达环点的点称为“环限制点”,这两种点在预处理中都要删除。

本沙茶以前用的一般方法是:先求图的传递闭包,找出所有的环点(能够到达自己的点),再从每个环点开始进行逆向遍历(将原图所有边反向,再遍历),找到所有的环限制点。该方法的时间复杂度高达O(N3),且写起来也爆麻烦。

其实,真正用于去环的最佳方法是拓扑排序!!!

首先将原图的所有边反向,然后进行拓扑排序,所有遍历到的点是保留下来的点,而没有遍历到的点就是环点或环限制点,需要删除。
【证明:环点显然是不可能被遍历到的,而在反向后的新图中,对于一个环限制点j,必然存在一个环点i能够到达它,而i不能被遍历到,故j也不能被遍历到。除了这两种点外,其它的点的所有前趋必然也都不是环点或环限制点(否则这些点就成了环限制点),因此只要入度为0(不存在前趋)的点能够遍历到,这些点也能够遍历到,而入度为0的点显然能遍历到,故这些点也能被遍历到。证毕】
由于求反向图和拓扑排序都可以在O(M)时间内完成,整个去环过程的时间复杂度就是O(M)的。

下面附上NOI2009 pvz代码:(注意,本题的第9个点是一个超级大数据,最后建出来的网络的边数将会达到300000,故MAXM取150000,另外,本题必须使用Dinic,SAP会超)
#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++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 602, MAXM = 150000, INF = ~0U >> 2;
struct link {
    
int kk;
    link 
*next;
*ed[MAXN], *ed2[MAXN];
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, sc[MAXN], hd[MAXN], tl[MAXN], st[MAXN], lev[MAXN], q[MAXN], hs[MAXN], pr[MAXN], ind[MAXN], now, res = 0;
bool vst[MAXN];
void init()
{
    freopen(
"pvz.in""r", stdin);
    
int n0, m0, A[20][30], num = 1, x, y, z;
    scanf(
"%d%d"&n0, &m0);
    re(i, n0) re(j, m0) A[i][j] 
= num++;
    n 
= n0 * m0 + 2; s = 0; t = n - 1; memset(ed, 0, n << 2); memset(ed2, 0, n << 2);
    re1(i, n 
- 2) {
        scanf(
"%d%d"&sc[i], &num);
        re(j, num) {
            scanf(
"%d%d"&x, &y); z = A[x][y];
            link 
*p1 = new link; p1->kk = i; p1->next = ed[z]; ed[z] = p1;
            link 
*p2 = new link; p2->kk = z; p2->next = ed2[i]; ed2[i] = p2; ind[z]++;
        }
    }
    re(i, n0) re2(j, 
1, m0) {
        z 
= A[i][j];
        link 
*p1 = new link; p1->kk = z; p1->next = ed[z - 1]; ed[z - 1= p1;
        link 
*p2 = new link; p2->kk = z - 1; p2->next = ed2[z]; ed2[z] = p2; ind[z - 1]++;
    }
    fclose(stdin);
}
inline 
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 prepare()
{
    
int front = 0, rear = -1;
    re1(i, n 
- 2if (!ind[i]) {q[++rear] = i; vst[i] = 1;}
    
int i, j;
    
for (; front<=rear; front++) {
        i 
= q[front];
        
for (link *p=ed2[i]; p; p=p->next) {
            j 
= p->kk; ind[j]--;
            
if (!ind[j]) {vst[j] = 1; q[++rear] = j;}
        }
    }
    memset(hd, 
-1, n << 2); memset(tl, -1, n << 2);
    re1(i, n 
- 2if (vst[i]) {
        
if (sc[i] > 0) {res += sc[i]; add_edge(s, i, sc[i]);}
        
if (sc[i] < 0) add_edge(i, t, -sc[i]);
    }
    re1(i, n 
- 2if (vst[i]) for (link *p=ed[i]; p; p=p->next) {
        j 
= p->kk;
        
if (vst[j]) add_edge(i, j, INF);
    }
}
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; hs[s] = INF; memset(vst, 0, n);
    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()) ;
}
void pri()
{
    freopen(
"pvz.out""w", stdout);
    printf(
"%d\n", res);
    fclose(stdout);
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    
return 0;
}

Feedback

# re: 最大闭合子图的预处理(去环)问题  回复  更多评论   

2012-01-28 12:54 by SHUXK
我用SAP真的过了

# re: 最大闭合子图的预处理(去环)问题  回复  更多评论   

2012-02-02 18:55 by Seter
囧,top+SAP真的是可以秒杀的……

# re: 最大闭合子图的预处理(去环)问题[未登录]  回复  更多评论   

2014-11-01 23:44 by 路人甲
2011年的文章,14年来挖个坟。什么叫“环点显然是不可能被遍历到的”?一点都不显然。
在有向图
M->A A->B B->C C->A B->N
中,ABC成环,M是进入环的节点,N是从环流出的节点。

你把这图反序后,跟原图拓扑一致,环点A,B,C可以从入度为0的N点开始遍历到。

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