[洛谷1345] 奶牛的电信 （最大流最小割）

洛谷1345

题意

给出点的个数，边的条数，源点和汇点。

分别给出与边相连的点，边权为1。

求最少删去多少点使得源点和汇点不连通。

思路

• 割点转割边+最大流最小割

• 最大流最小割定理：最大流=最小割

• 割：删去一些边使得源点和汇点不连通

题目是求删点，最大流最小割算法删的是边，所以要割点转化为割边（最大流最小割其实并不能算一个算法，只是将求最小割转化为求最大流）

建图思想

将一个点拆成两个点，其中一个点负责连接入边，另外一个点负责连接出边，拆成的两个点之间边权为1，表示只能一个点只能删一次（如果这条边被删了，入边和出边无法连通表示点被删除）。由于求的是删除点的个数，其他的边置为INF。

举个栗子

代码实现

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define sf(x) scanf("%d",&(x))

const int MAXN=1e2+5;
const int MAXM=6e2+5;
const int INF=1e8+10;

int N,M,S,T;
struct node{int v,flow,next;}edge[(MAXM*4+MAXN*2)];

int head[MAXN<<1],cur[MAXN<<1],num=0;//注意这里必须从0开始

inline void add(int x,int y,int z)
{
    edge[num].v=y;edge[num].flow=z;
    edge[num].next=head[x];head[x]=num++;
}
queue<int> q;
int deep[MAXN<<1];

bool BFS()
{
    memset(deep,0,sizeof(deep));
    deep[S]=1;
    q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
            if(!deep[edge[i].v]&&edge[i].flow)
            {
                deep[edge[i].v]=deep[u]+1;
                q.push(edge[i].v);
            }
    }
    return deep[T];
}

int DFS(int now,int nowflow)
{
    if(now==T)    return nowflow;
    int totflow=0;//从这个点总共可以增广多少流量
    for(int i=cur[now];i!=-1;i=edge[i].next)
    {
        cur[now]=i;//当前弧优化，记录压榨到哪条边

        if(deep[edge[i].v]==deep[now]+1&&edge[i].flow)//只有满足距离要求与流量要求的点才能进行增广
        {
            int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));

            if(!canflow)continue;//当可增广的流量大于0，更新
            edge[i].flow-=canflow;edge[i^1].flow+=canflow;//增广
            totflow+=canflow;
            nowflow-=canflow;
            if(nowflow<=0) break; //当前点已经没有流量  快100ms
        }
    }
    if(!totflow)deep[now]=-2;//爆点优化，该点已经没有剩余流量，证明不必要的点下一次不需要遍历
    return totflow;//返回总流量，多路增广优化
}
void Dinic()
{
    int ans=0;
    while(BFS())//每次构造分层图
    {
        puts("bfs");
//        for(int i=1;i<=N+N;i++)cout<<deep[i]<<" ";
//        cout<<endl;
        memcpy(cur,head,sizeof(head)); //当前弧优化
        ans+=DFS(S,INF);//进行增广
        puts("dfs");
//        for(int i=0;i<)
    }
    printf("%d",ans);
}

int main()
{
    sf(N);sf(M);sf(S);sf(T);
    S+=N;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=N;i++){
        add(i,i+N,1);
        add(i+N,i,0);
    }

    for(int i=1,x,y,z;i<=M;i++)
    {
        sf(x);sf(y);
        add(y+N,x,INF);
        add(x,y+N,0);
        add(x+N,y,INF);
        add(y,y+N,0);
    }
    Dinic();
    return  0;
}

# [洛谷1345] 奶牛的电信 （最大流最小割）