ZOJ 2182 Cable TV Network（无向图点割-最大流）

2020-12-13 16:27

阅读：548

标签：style class blog code http tar

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2182

题意：给出一个无向图，问最少删掉多少个顶点之后图变得不连通？

思路：将原图每个点拆点(i,i+n)，连边，对原图的边(u,v)，连边,。然后对于每对顶点(i,j)跑最大流(i+n,j)。所有最大流的最小值即为答案。

struct node
{
    int v,cap,next;
};




node edges[N*10];
int head[N],e;
int curedge[N],h[N],num[N],pre[N];
int s,t;




void add(int u,int v,int cap)
{
    edges[e].v=v;
    edges[e].cap=cap;
    edges[e].next=head[u];
    head[u]=e++;
}




void Add(int u,int v,int cap)
{
    add(u,v,cap);
    add(v,u,0);
}




int Maxflow(int s,int t,int n)
{
    clr(h,0); clr(num,0);
    int i;
    FOR0(i,n+1) curedge[i]=head[i];
    int u=s,Min,k,x,ans=0;
    while(h[u]0&&h[u]==h[edges[i].v]+1)
            {
                break;
            }
        }
        if(i!=-1)
        {
            curedge[u]=i;
            pre[edges[i].v]=u;
            u=edges[i].v;
        }
        else
        {
            if(--num[h[u]]==0) break;
            curedge[u]=head[u];
            x=n;
            for(i=head[u];i!=-1;i=edges[i].next)
            {
                k=edges[i].v;
                if(edges[i].cap>0&&h[k]

ZOJ 2182 Cable TV Network（无向图点割-最大流）,搜素材,soscw.com

ZOJ 2182 Cable TV Network（无向图点割-最大流）

标签：style class blog code http tar

原文地址：http://www.cnblogs.com/jianglangcaijin/p/3799816.html

上一篇：深入解析Windows操作系统笔记——CH3系统机制

下一篇：解决 Attempting to destroy the window while drawing!

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：ZOJ 2182 Cable TV Network（无向图点割-最大流）
文章链接：http://soscw.com/essay/36149.html

亲，登录后才可以留言！

ZOJ 2182 Cable TV Network（无向图点割-最大流）

评论

热门文章

推荐文章

最新文章

置顶文章