[POJ][1966][网络流] Cable TV Network

题目大意：

给出一个无向图，求解至少删去多少个点，才能使网络不连通。

思路：

就是求割点集中点的数量。利用网络流求解，以任意一点为源点，遍历汇点，最大流的最小值即是需要删去的点的个数。但是需要额外注意三个地方：

需要拆点，将每个点拆成两个相互之间通路容量为1的点。不同点之间建立的通路的容量则为无限。

由于源点可能是割点集中的点，这样计算出的结果可能会大于实际，所以源点也要遍历。

再就是输入样例用第三个例子，这算是特殊情况。整个网络就是一个割点集时，源点汇点无论如何取，结果都会比实际值大。这样的情况也有比较明显的特征，即是最大流的最小值会大于INF，换句话说，网络中的各点都是两两相连的。这时，直接输出节点数即可。

代码：

#include
using namespace std;
#define DATASIZE 50*2
#define INF 1000
int map[DATASIZE+1][DATASIZE+1],backup_map[DATASIZE+1][DATASIZE+1],f[DATASIZE+1],pre[DATASIZE+1],queue[DATASIZE],start,end,n,m;
//n表示边的个数,m表示点的个数,map表示残留网络，f[i]表示处于i点时的最大剩余容量。 
int bfs()
{
    memset(pre,0,sizeof(pre));
    memset(queue,0,sizeof(queue));
    int now=0,tail=0;
    f[start]=INF;
    queue[tail++]=start;
    while(tail-now)
    {
        int head=queue[now++];
        if(head==end)
            return f[end];
        for(int i=1;i<=m*2;i++)
        //由于拆点操作，节点个数翻倍。 
            if(!pre[i]&&map[head][i])
            {
                f[i]=f[head]=INF?m:min);
        //输出时判断下min与INF是否相等，目的是判断当前是否处于整个网络就是一个割点集这种特殊情况。 
    }
}

后记：

提交后时间为250ms，由于是EK是O(VE^2)的复杂度，相比较SAP的O(EV^2)有不小的差距。曾设想进行优化，由于每次求最大流都要两层循环backup_map[][]初始化残留网络map[][]，于是就想从矩阵复制入手。

思考了会，想起了memcpy，它可以进行连续空间的复制，但由于数组只有一维度上是连续的，所以还是免不了外层循环。满怀期待的尝试，结果却令人大跌眼镜，782ms！这货比for循环还慢，跟它兄弟memset差太多了。

之前看过NotOnlySuccess的《网络流的几个常见算法》，结论上说基本没题会去卡SAP，而却EK很悲剧，看来又得重新写模板了。

下面是用《网络流的几个常见算法》里的“sap+gap优化”模板写的代码，时间从250ms降到了141ms，非常可观的优化。美中不足的是这模板毕竟属于别人，风格上差别太大。虽然代码短小，但是使用了goto无疑是种缺憾。想手动改成递归，效率低些不要紧，但发现无从下手，我对sap的理解还太嫩，不会改啊。

#include
using namespace std;
#define MAXN 50*2
#define INF MAXN+1
int map[MAXN][MAXN],backup_map[MAXN][MAXN];
int gap[MAXN],dis[MAXN],pre[MAXN],cur[MAXN];
//非负整数dis[i]描述i点到汇点的最少弧的数量，初始化均为0。 
int m,n;
int sap(int s,int t,int total)
//s源点，t汇点，total节点的个数 
{
    memset(cur,0,sizeof(cur));
    memset(dis,0,sizeof(dis));
    memset(gap,0,sizeof(gap));
    int u=pre[s]=s,maxflow=0,aug=-1;
    gap[0]=total;
    while(dis[s]map[u][v])
                    aug=map[u][v];
                pre[v]=u;
                u=cur[u]=v;
                if(v==t) 
                {
                    maxflow+=aug;
                    for(u=pre[u];v!=s;v=u,u=pre[u])
                    {
                        map[u][v]-=aug;
                        map[v][u]+=aug;
                    }
                    aug=-1;
                }
                goto loop;
            }
        int mindis=total-1;
        for(int v=0;vdis[v])
            {
                cur[u]=v;
                mindis=dis[v];
            }
        if(!(--gap[dis[u]]))
            break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return maxflow;
}
int solved(int s,int e)
//计算s为源点，e为汇点的最大流。 
{
    for(int i=0;i=INF?m:min);
        //输出时判断下min与INF是否相等，目的是判断当前是否处于整个网络就是一个割点集这种特殊情况。 
    }
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注