精华内容
下载资源
问答
  • 网络流 最小割

    2017-03-08 21:02:05
    标签:网络流 最小割 原题 洛谷P2057 善意的投票题目描述幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见,但是为了照顾...

    标签:网络流 最小割

    原题 洛谷P2057 善意的投票

    题目描述

    幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说,这个问题并不是很重要,于是他们决定发扬谦让精神。虽然每个人都有自己的主见,但是为了照顾一下自己朋友的想法,他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。

    我们的问题就是,每位小朋友应该怎样投票,才能使冲突数最小?

    输入输出格式

    输入格式:
    文件的第一行只有两个整数n,m,保证有2≤n≤300,1≤m≤n(n-1)/2。其中n代表总人数,m代表好朋友的对数。文件第二行有n个整数,第i个整数代表第i个小朋友的意愿,当它为1时表示同意睡觉,当它为0时表示反对睡觉。接下来文件还有m行,每行有两个整数i,j。表示i,j是一对好朋友,我们保证任何两对i,j不会重复。

    输出格式:
    只需要输出一个整数,即可能的最小冲突数。

    输入输出样例

    输入样例#1:
    3 3
    1 0 0
    1 2
    1 3
    3 2
    输出样例#1:
    1
    说明

    2≤n≤300,1≤m≤n(n-1)/2。

    要么投睡觉要么不睡,所以应分成两个集合,因为可以跟着好朋友改意见,所以可以连着边的人都可以投同一个票。每个人只有两种选择,所以肯定和s点或t点连着,所以如果割变是与源汇点连着,则算是与自己的意愿冲突,如果割在朋友间则是与朋友的冲突。每割断一对好友或自身意愿。冲突数加一,所以就是求最小割。最小割等于最大流,用dinic即可。(dinic请看模板dinic模板
    注意的是一对好友之间可以互相改意见,所以直接建双向边(注意是双向边,和原来算法的反向边区分好,这是本题需要,反向边是为了保证算法正确,都要建,刚开始我就被坑了)。自己再建一个s点表示一种最初观点相同的人,建一个t点表示另一种。我是投1的连s,投0的人连t。
    代码在此

    #include<iostream>
    #include<cstdio>
    #include<queue>
    #include<cstring>
    #define N 310
    #define M 100000
    using namespace std;
    
    int m,n,ans;
    queue<int>team;
    struct E{
        int to,next,c;
    }a[M*2];int last[N],dis[N],cnt;
    
    void build(int u,int v,int c)
    {
        a[++cnt].to=v;a[cnt].next=last[u];
        a[cnt].c=c;last[u]=cnt;
        a[++cnt].to=u;a[cnt].next=last[v];
        a[cnt].c=0;last[v]=cnt;
    }
    bool bfs()
    {
        memset(dis,-1,sizeof(dis));
        team.push(305);dis[305]=0;
        while(!team.empty()){
            int x=team.front();team.pop();
            for(int i=last[x];i;i=a[i].next){
                if(a[i].c&&dis[a[i].to]==-1){
                    dis[a[i].to]=dis[x]+1;
                    team.push(a[i].to);
                }       
            }
        }
    
        return dis[306]>-1;
    }
    
    int dfs(int x,int f)
    {
        if(x==306)return f;
        int now=0,b;
        for(int i=last[x];i;i=a[i].next)
        if(a[i].c&&dis[a[i].to]==dis[x]+1){
        b=dfs(a[i].to,min(f-now,a[i].c));
        a[i].c-=b;a[i^1].c+=b;now+=b;
        if(now==f)break;    
        }
        if(!now)dis[x]=-1;
        return now;
    }
    int main()
    {
        freopen("in.txt","r",stdin);
        freopen("1.txt","w",stdout); 
        scanf("%d%d",&n,&m);
         ans=0; cnt=1;
        for(int i=1;i<=n;++i){
            int vot;scanf("%d",&vot);
            if(vot==1)build(305,i,1);
            else      build(i,306,1);
        }
    
        for(int i=1;i<=m;++i){
        int u,v;    
        scanf("%d%d",&u,&v);
        build(u,v,1);build(v,u,1);//双向边。注意build函数里的是反边 
        }
        while(bfs())
        ans+=dfs(305,0x7fffffff);
        printf("%d\n",ans);
        return 0;
    }
    
    展开全文
  • 网络流最小割的应用

    2017-07-21 19:33:31
    在竞赛中最小割的应用,和各种奇怪的模型等证明,值得一看
  • Gym-101484H Eating Pie [网络流最小割]

    题意:A和B去商店买东西,A只能买A购物清单上的商品,B同理,并且一个商品只能被一个人购买,商店一共n个物品,当第i个物品与第i+1个物品被同一个人购买时能获得ci的价值,求A和B最大的价值和。

    题解:首先我们将相邻物品相同的情况的价值加起来,然后对于A能够同时购买的相邻物品价值,与B能够同时购买的相邻物品价值,先全部加入答案中。之后我们建图求最小不能相容的价值,减去这部分价值就是答案。

    建图如下。

    如样例

    /*
    3 3 2 2
    1 2
    2 3
    1 2 3
    1 2
    */
    我们可以得到如下建图:


    所以能够得到最小割为1.

    详细见代码。

    AC代码:

    #include<cstdio>    
    #include<cstring>    
    #include<queue>   
    #include<algorithm> 
    #include<cmath>    
    using namespace std;    
    const int Ni = 3005;    
    const int MAX = 1<<26;    
    struct Edge{    
        int u,v,c;    
        int next;    
    }edge[20*Ni];    
    int n,m;    
    int edn;//边数    
    int p[Ni];//父亲    
    int d[Ni];    
    int sp,tp;//原点,汇点    
       
    void addedge(int u,int v,int c)    
    {    
        edge[edn].u=u; edge[edn].v=v; edge[edn].c=c;    
        edge[edn].next=p[u]; p[u]=edn++;    
       
        edge[edn].u=v; edge[edn].v=u; edge[edn].c=0;    
        edge[edn].next=p[v]; p[v]=edn++;    
    }    
    int bfs()    
    {    
        queue <int> q;    
        memset(d,-1,sizeof(d));    
        d[sp]=0;    
        q.push(sp);    
        while(!q.empty())    
        {    
            int cur=q.front();    
            q.pop();    
            for(int i=p[cur];i!=-1;i=edge[i].next)    
            {    
                int u=edge[i].v;    
                if(d[u]==-1 && edge[i].c>0)    
                {    
                    d[u]=d[cur]+1;    
                    q.push(u);    
                }    
            }    
        }    
        return d[tp] != -1;    
    }    
    int dfs(int a,int b)    
    {    
        int r=0;    
        if(a==tp)return b;    
        for(int i=p[a];i!=-1 && r<b;i=edge[i].next)    
        {    
            int u=edge[i].v;    
            if(edge[i].c>0 && d[u]==d[a]+1)    
            {    
                int x=min(edge[i].c,b-r);    
                x=dfs(u,x);    
                r+=x;    
                edge[i].c-=x;    
                edge[i^1].c+=x;    
            }    
        }    
        if(!r)d[a]=-2;    
        return r;    
    }    
       
    int dinic(int sp,int tp)    
    {    
        int total=0,t;    
        while(bfs())    
        {    
            while(t=dfs(sp,MAX))    
            total+=t;    
        }    
        return total;    
    } 
    
    
    int a[505],b[505],s[1005],point[505],tot=1;
    int val[505][505];//记录价值 
    int main()
    {
    	int k,n,A,B;
    	scanf("%d%d%d%d",&k,&n,&A,&B);
    	for(int i=0;i<A;i++)
    	{
    		int x;
    		scanf("%d",&x);
    		a[x]=1;
    	}
    	for(int i=0;i<B;i++)
    	{
    		int x;
    		scanf("%d",&x);
    		b[x]=1;
    	}
    	int ans=0;
    	for(int i=0;i<n;i++)
    		scanf("%d",&s[i]);
    	for(int i=0;i<n-1;i++)
    	{
    		int x;
    		scanf("%d",&x);
    		if(s[i]==s[i+1])
    			ans+=x;
    		else val[min(s[i],s[i+1])][max(s[i],s[i+1])]+=x;
    	}
    	for(int i=1;i<=k;i++)point[i]=tot++;
    	edn=0;sp=0;tp=n*3+2; 
     	memset(p,-1,sizeof(p)); 
    	for(int i=1;i<=k;i++)
    		for(int j=i+1;j<=k;j++)
    			if(val[i][j]&&a[i]&&a[j])
    			{
    				ans+=val[i][j];
    				int id=tot++;
    				addedge(sp,id,val[i][j]);
    				addedge(id,point[i],MAX);
    				addedge(id,point[j],MAX);
    			}
    	for(int i=1;i<=k;i++)
    		for(int j=i+1;j<=k;j++)
    			if(val[i][j]&&b[i]&&b[j])
    			{
    				ans+=val[i][j];
    				int id=tot++;
    				addedge(point[i],id,MAX);
    				addedge(point[j],id,MAX);
    				addedge(id,tp,val[i][j]);
    			}
    	printf("%d\n",ans-dinic(sp,tp));
    }
    
    /*
    3 3 2 2
    1 2
    2 3
    1 2 3
    1 2
    */



    展开全文
  • 2.通络流大小==最小割大小,一个网络流值对应多种最小割方案 3.Dinic算法跑完后求出网络流值,会把图中所有的满流的边删掉,最小割一定是由满流的边组成,但不是任意的几个满流的边都能4.组成最小...

    题目:BZOJ-1797

    题解:关于最小割可以去这里看一下,对话形式的解释,讲的挺清楚的。

    对于本题:

    1.最小路劲的切断方案:就是指最小割,包不包括这条边就是指最小割的方案中有没有一个包含这条边
    2.通络流大小==最小割大小,一个网络流值对应多种最小割方案
    3.Dinic算法跑完后求出网络流值,会把图中所有的满流的边删掉,最小割一定是由满流的边组成,但不是任意的几个满流的边都能4.组成最小割
    4.Dinic算法跑完后剩下的残图,残图中有多个连通块,如果对于一条边他的起终点在两个不同的连通块中,那么就说明这条边是满流,构成了最大流,那么他可以参与构成最小割,如果这条边的起点在s所在连通块,终点在t所在连通块内,那么就说明这条边是必须被删除的满流边,是必须参与构成最小割的

    (相当于:①对于任意一条满流边(u,v),(u,v)能够出现在某个最小割集中,当且仅当id[u]!=id[v];
    ②对于任意一条满流边(u,v),(u,v)必定出现在最小割集中,当且仅当id[u]==id[s]且id[v]==id[t]。)

    那么这个题目就可以先跑一遍Dinic求出残图,然后再在残图中跑Tarjan,把联通块找出来,记录节点所在联通块编号,然后再按边查询这道题就解决了~

    代码:

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<set>
    #include<map>
    #include<vector>
    #include<stack>
    #define N 100005
    #define M 100005
    #define INF 0x7fffffff
    using namespace std;
    int n,m,s,t,c,tot,num;
    int head[N],cur[N],dfn[N],low[N],deep[N],belong[N];
    bool vis[N];
    struct ljh
    {
        int next,to,w,from;
    }e[2*M];
    stack<int>ss;
    inline void add(int x,int y,int z)
    {
        e[c].next=head[x];
        e[c].from=x;
        e[c].to=y;
        e[c].w=z;
        head[x]=c++;
    }
    inline void init()
    {
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(belong,0,sizeof(belong));
        tot=0;
        c=0;
        num=0;
    }
    bool bfs(int s,int t)
    {
        queue<int>q;
        memset(deep,0,sizeof(deep));
        deep[s]=1;
        q.push(s);
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=head[x];i!=-1;i=e[i].next)
            {
                int nex=e[i].to;
                if(e[i].w!=0&&deep[nex]==0)
                {
                    deep[nex]=deep[x]+1;
                    q.push(nex);
                }
            }
        }
        return deep[t]!=0;
    }
    int dfs(int x,int t,int maxflow)
    {
        if(x==t)return maxflow;
        int ans=0;
        for(int i=cur[x];i!=-1;i=e[i].next)
        {
            int nex=e[i].to;
            if(deep[nex]!=deep[x]+1||ans>=maxflow||e[i].w<=0)continue;
            cur[x]=i;
            int k=dfs(nex,t,min(e[i].w,maxflow-ans));
            e[i].w-=k;
            e[i^1].w+=k;
            ans+=k;
        }
        if(ans==0)deep[x]=-2;
        return ans;
    }
    void Dinic(int s,int t)
    {
        while(bfs(s,t))
        {
            memcpy(cur,head,sizeof(head));
            dfs(s,t,INF);
        }
    }
    void Tarjan(int x)
    {
        low[x]=dfn[x]=++tot;
        ss.push(x);
        vis[x]=1;
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            if(e[i].w)//判断一下,这条边必须是残留的边才可以更新联通块
            {
    		    int v=e[i].to;
    		    if(!dfn[v])
    		    {
    		        Tarjan(v);
    		        low[x]=min(low[x],low[v]);
    		    }
    		    else if(vis[v]==1)low[x]=min(low[x],dfn[v]);
            }
        }
        if(low[x]==dfn[x])//这里没注意,找bug找到自闭
        {
            int nex;
            num++;
            do
            {
                nex=ss.top();
                ss.pop();
                vis[nex]=0;
                belong[nex]=num;
            }while(!ss.empty()&&nex!=x);
        }
        return;
    }
    int main()
    {
        while(~scanf("%d%d%d%d",&n,&m,&s,&t))
        {
            init();
            for(int i=1;i<=m;i++)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                add(x,y,z);
                add(y,x,0);
            }
            Dinic(s,t);
            for(int i=1;i<=n;i++)
                if(!dfn[i])
                    Tarjan(i);
            for(int i=0;i<c;i+=2)
            {
                if(e[i].w>0)printf("0 0\n");//说明那条边根本就没走
                else
                {
                    if(belong[e[i].from]!=belong[e[i].to])printf("1 ");
                    else printf("0 ");
                    if(belong[e[i].from]==belong[s]&&belong[e[i].to]==belong[t])printf("1\n");
                    else printf("0\n");
                }
            }
        }
     }

     

    展开全文
  • 前置知识:网络最大流(最好是dinic算法),最大流最小割定理。 一、割边最少的最小割 题目: hdu3987 http://acm.hdu.edu.cn/showproblem.php?pid=3987 hdu6214 http://acm.hdu.edu.cn/showproblem.ph...

    (12.6)
    今天看了下网络流,本想写一篇博客,但是想了想,画图太费劲,证明也不算特别难,那就先咕着了。
    前置知识:网络最大流(最好是dinic算法),最大流最小割定理
    一、割边最少的最小割
    题目:
    hdu3987 http://acm.hdu.edu.cn/showproblem.php?pid=3987
    hdu6214 http://acm.hdu.edu.cn/showproblem.php?pid=6214 (双倍经验)

    方法一:(一次dinic)

    我们首先考虑,如何在求最大流的同时兼顾最小割的边数。

    第一感觉是类似费用流,给每一条边加一维费用,但仔细思考后发现不用。我们完全可以直接对于每一条边的容量+1,那么最后所求出的最大流一定会保证最小割的边数最少。证明:

    设原图最小割为S,那么我们对于每一条边容量+1后,当前图最小割变为S + P(P为最小割的边数),显然可以得到,当P最小时,取得当前图的最小割,即保证了最小割的最少割边。

    但是,这样做会改变原图的最小割。当然,我们可以做两次dinic,但是这需要你常数够好不怕卡常。如果我们只做一次dinic,显然我们需要做到的是:去掉边数对答案的影响。这里有一个操作:

    将原图中每一条边的容量*(maxp + 1)(maxp为图中最大边数)+ 1

    那么当前图的最小割为S * (maxp + 1) + P(P为最小割的边数)

    显然P < maxp + 1,那么我们对当前的最小割除以(maxp + 1)就是原图的最小割取模(maxp + 1)就是原图最小割的最少割边

    代码不想写了。

    方法二:(两次dinic)

    我们在第一次dinic求出来最大流时,由于最小割中的边都是满流边,那么问题转化为,最少删掉几条满流边可以使图不连通。

    仔细想想,当前那个问题不也是求一个最小割吗?那么我们不妨重新构图(其实只是修改了容量),对于满流边将它的容量改为1,其它边的容量改为无穷大。这样,求出来的最小割即为最少割边啦。

    代码也不写啦,都是板子。

    二、最小割树

    咕咕咕!

    展开全文
  • 有一个与最大关系密切的问题:最小割。就是把所有的顶点分成两个集合S和T=V-S,其中源点s在集合S中,汇点t在集合T中。 如果把“起点在S中,终点在T中”的边都删除,就无法从s到达t了。我们把这样的集合划分(S,T...
  • 题目大意:给出一个图,每个边有权值。最后再给一条边。问最少去掉多少条边,可以使得这条新加的边既可能...所以就将所有的边权比这条边小的边建图,然后泡最小割,使得这两给点不连起来。这就是满足去掉最少的边让它
  • vijosP1524网络流最小割

    2015-01-03 17:31:41
    由于yxy小朋友做了一些不该做的事,他被jzp关进了一个迷宫里。由于jzp最近比较忙,疏忽大意了一些,yxy可以在迷宫中任意走动。整个迷宫可以被看作是一个...现在jzp正在忙,请你编一个程序算出使yxy无法逃离迷宫的最小
  • 一个无向图,求最小的平均:,其中,wi表示边权,该表达式的意思就是选择某些边集构成S-T,使得平均割最小。 分析:0-1分数规划问题,设,则令mincut=因为ci只能取0或1所以转换模型,边权值变为
  • 具体思路:网络流最小割等于玩网络流的最大流量,注意拆点,以及拆点后边连的时候是拆点后第二个点连向目的地。 AC代码: #include&lt;stdio.h&gt; #include&lt;string.h&gt; #include&lt;...
  • 定理:从s跑到t的最大就是s到t的最小割,最大=最小割从s跑到t的最大就是s到t的最小割,最大=最小割从s跑到t的最大就是s到t的最小割,最大=最小割 感性的理解:最大包含所有s流向t的可能最大包含所有s流向...
  • POJ 3469 网络流最小割

    2015-02-10 15:43:00
    将两个CPU分别视作源点和汇点 对于那些不在同一个CPU中的模块会产生的代价作为一条双向的容量弧 这里每个模块可以在任意一个...根据最大=最小割的原理,这里相当于是在求最大 1 #include <cstdio> ...
  • 在运行完网络流算法之后,在残量网络上,s和t之间不连通了进行一边dfs/bfs,求出从s出发能到达的点集S,和不能到达的点集T我们割掉了一组边,把原图划分成了S和T两个点集所有从S跨越到T的满流边构成了一个最小割方案...
  • HDU3491 网络流最小割模型

    千次阅读 2010-11-27 09:48:00
    最大流最小割模型
  • 小白在图论课上学到了一个新的概念——最小割,下课后小白在笔记本上写下了如下这段话: “对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点s,t不在同一个部分中,则称这个划分是关于s,t的割...
  • 这题难点在于建图。参考了网上大牛的建图,膜拜下orz 首先这类题,分成两个集合A,B 集合内部的点都是不相交的。 然后对于每一个点,有三种选择,金,银,...最小割割去的都是不要的,所以答案为Sum-最小割。 这个
  • hdu1569网络流最小割

    千次阅读 2012-08-26 00:40:57
    首先黑白染色,源点到黑点连条边,值为格子数值,然后白色点到汇点也连条这样的边,然后每个黑点对与其相连的白点连条无穷大的边,然后求个最小割,答案就是所有格子数值和减去这个最小割。#include #include int n,...
  • 建完图之后跑最小割即可。 自己画了个图,应该会更形象些。 大神题解 http://blog.csdn.net/PoPoQQQ/article/details/43968017 代码如下: #include #include #include using namespace std; ...
  • 【POJ1815】Friendship 网络流最小割

    千次阅读 2015-01-07 10:59:51
    题解:最小割,首先我们拆点,两部分流量为1来满足性质,然后连inf的联通边。 然后跑一遍就出来需要几个人了。 如果是inf就NO answer 然后我们从小到大枚举哪个人在最小割集里面,即把此人删掉再跑,...
  • 对于两个01变量,如果我们...然后我们就可以用最大最小割)初步处理二元关系了。 这时2e=v1+v2-v3-v4=-K 这里说的是如果K = v3 + v4 - v1 - v2(相异减相同)小于0,那...
  • bzoj2521 [Shoi2010]最小生成树 原题地址:http://www.lydsy.com/JudgeOnline/problem.php?id=2521 题意: 某一个图可能有多种不同的最小生成树。例如,下面图 3中所示的都是图 2中的无向图的最小生成树: ...
  • 现在我们考虑求出最小割的必割边,若这些必割边的容量之和就是最小割那么这就是唯一的方案。 如何求出必割边? ∗ * ∗ 结论 : : : 对于一条边 x , y x,y x , y ,在残量网络上 s s s 可以到达 x x x 且 y y y ...
  • 即:以(1,1)为源,(n,m)为汇,求该图最小割  不过由于节点过多,直接对输入的图求最小割的话会超时  转化:求它的对偶图,然后求最短路,见图,红字为点编号,绿线为建的边(边权为其经过的原图的边的权值) 注意...
  • 需要消灭他们,因此要在某些行(或列)安装激光枪,并且该激光枪只能杀死该行(或列)的火星人,在某列(或行)安装一个激光枪会产生花费,总的费用为这些费用的乘积,求把所有火星人都杀死的最小总花费。...
  • bzoj3894 文理分科(网络流最小割

    千次阅读 2017-02-07 15:41:25
    要额外收益,与T连通表示要额外收益先算出总收益,在用最小割减去即可。 4.于是我们可以列出方程: c+d=B[i]+WB(学生i学文,不要额外收益,损失学理收益,损失额外收益) a+b=A[i](学生i学理,要额外收益,损失...
  • 【题解】【网络流最小割】 【由最小生成树(kruskal)可知,若一条边必出现在一个图的最小生成树中,当且仅当用小于当前边的边不可使这条边控制的两个点相连 】 【由这一性质可得网络流建图方法:将原图中所有...
  • 建立源点和汇点之后,就变成了裸的的最小割问题,最大点权独立集 = 总权值-最小点权覆盖值(最小割),建图如下。 总结:经典的最小割模型,对于一种情况的最大能量,就是该图的能量总和-最小割。 代码:待补...
  • HDU 3251 Being a Hero 网络流 最小割

    千次阅读 2011-08-25 21:09:31
    /* 题意:给你f个可选城市,每个城市都有其价值w0,国王的城市在1,现在国王不想见到你(国王不想通过某种路径到达你选定的城市)——将你选的若干城市隔离出去,每条道路隔断...题解:网络流模型题,将所有可选点连入超

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,962
精华内容 4,384
关键字:

网络流最小割