头像

acwing_zyy

$\color{Red}{AcWing\, University}$




离线:3分钟前


最近来访(487)
用户头像
一切皆有可能
用户头像
有机物
用户头像
Vertex
用户头像
我是菜狗啊啊啊啊啊
用户头像
牛牛蒟蒻
用户头像
BB_7
用户头像
艾伦_0
用户头像
不高兴的兽奶
用户头像
acwing_xyy
用户头像
种花家的兔兔
用户头像
18985082146
用户头像
瓜瓜
用户头像
仙贝
用户头像
violet_garden
用户头像
dhxdl666
用户头像
DreamFather
用户头像
R虎虎生威R
用户头像
Dragonite
用户头像
五柳先生
用户头像
是这样的捏


acwing_zyy
3分钟前

题目链接

2191. 数字梯形问题

给定一个由 $n$ 行数字组成的数字梯形如下图所示。

梯形的第一行有 $m$ 个数字。

从梯形的顶部的 $m$ 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

规则 $1$:从梯形的顶至底的 $m$ 条路径互不相交。

规则 $2$:从梯形的顶至底的 $m$ 条路径仅在数字结点处相交。

规则 $3$:从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

image

对于给定的数字梯形,分别按照规则 $1$,规则 $2$,和规则 $3$ 计算出从梯形的顶至底的 $m$ 条路径,使这 $m$ 条路径经过的数字总和最大。

输入格式

第 $1$ 行中有 $2$ 个正整数 $m$ 和 $n$,分别表示数字梯形的第一行有 $m$ 个数字,共有 $n$ 行。

接下来的 $n$ 行是数字梯形中各行的数字。第 $1$ 行有 $m$ 个数字,第 $2$ 行有 $m+1$ 个数字,以此类推。

输出格式

将按照规则 $1$,规则 $2$,和规则 $3$ 计算出的最大数字总和输出,每行输出一个最大总和。

数据范围

$1 \le n,m \le 20$,
梯形中的数字范围 $[1,1000]$。

输入样例:

2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1

输出样例:

66
75
77

解题思路

费用流,最大权不相交路径

建图
对于限制一,先建立源点 $s$ 和汇点 $t$,由于点受到限制且费用没法表示,所以需要拆点,即拆分为入点和出点,每个点的入点向其出点连边,由于每个点只能用一次,所以容量为 $1$,费用为点权,由于第一行人数已经固定为 $1$,从 $s$ 到所有第一行的点连边,容量为 $1$,费用为 $0$,最后一行的所有点的出点向 $t$ 连边,容量为 $1$,费用为 $0$
其他两个限制相应地放开容量即可
$\color{red}{为什么?}$
把可行流的轨迹当作人的行动轨迹,不难发现,此时对于限制一,如果某个点的入点和出点有流量的话,且只会经过一次,表示选择该点且计算其费用,由于第一行已经确定了,从 $s$ 出发的边都会
满流,即最后达到最大流时求解最大费用即为不相交路径最大权,故可行流与实际问题是一一对应的,其他两个限制同理

  • 时间复杂度:$O(k\times (n+m)\times f)$

代码

// Problem: 数字梯形问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2193/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=590*2+5,M=(20+39+590+590*2+10)*2,inf=1e9;
int m,n,cost[40][40],S,T,id[40][40],cnt;
int h[N],f[M],w[M],ne[M],e[M],idx;
int incf[N],pre[N],d[N],q[N];
bool st[N];
void add(int a,int b,int c,int d)
{
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa()
{
    memset(d,-0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    d[S]=0,incf[S]=inf,q[0]=S;
    int hh=0,tt=1;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N)hh=0;
        st[x]=false;
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]<d[x]+w[i]&&f[i])
            {
                d[y]=d[x]+w[i];
                pre[y]=i;
                incf[y]=min(incf[x],f[i]);
                if(!st[y])
                {
                    q[tt++]=y;
                    if(tt==N)tt=0;
                    st[y]=true;
                }
            }
        }
    }
    return incf[T]>0;
}
int EK()
{
    int cost=0;
    while(spfa())
    {
        int t=incf[T];
        cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1])f[pre[i]]-=t,f[pre[i]^1]+=t;
    }
    return cost;
}
int main()
{

    scanf("%d%d",&m,&n);
    S=++cnt,T=++cnt;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m+i-1;j++)
        {
            scanf("%d",&cost[i][j]);
            id[i][j]=++cnt;
        }

    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m+i-1;j++)
        {
            add(id[i][j]<<1,id[i][j]<<1|1,1,cost[i][j]);
            if(i==1)
                add(S,id[i][j]<<1,1,0);
            if(i<n)
                add(id[i][j]<<1|1,id[i+1][j]<<1,1,0),
                add(id[i][j]<<1|1,id[i+1][j+1]<<1,1,0);
            if(i==n)
                add(id[i][j]<<1|1,T,1,0);
        }
    printf("%d\n",EK());

    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m+i-1;j++)
        {
            add(id[i][j]<<1,id[i][j]<<1|1,inf,cost[i][j]);
            if(i==1)
                add(S,id[i][j]<<1,1,0);
            if(i<n)
                add(id[i][j]<<1|1,id[i+1][j]<<1,1,0),
                add(id[i][j]<<1|1,id[i+1][j+1]<<1,1,0);
            if(i==n)
                add(id[i][j]<<1|1,T,inf,0);
        }
    printf("%d\n",EK());

    memset(h,-1,sizeof h);
    idx=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m+i-1;j++)
        {
            add(id[i][j]<<1,id[i][j]<<1|1,inf,cost[i][j]);
            if(i==1)
                add(S,id[i][j]<<1,1,0);
            if(i<n)
                add(id[i][j]<<1|1,id[i+1][j]<<1,inf,0),
                add(id[i][j]<<1|1,id[i+1][j+1]<<1,inf,0);
            if(i==n)
                add(id[i][j]<<1|1,T,inf,0);
        }
    printf("%d\n",EK());
    return 0;
}



acwing_zyy
11小时前

题目链接

2193. 分配问题

有 $n$ 件工作要分配给 $n$ 个人做。

第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{ij}$。

试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案。

对于给定的 $n$ 件工作和 $n$ 个人,计算最优分配方案和最差分配方案。

输入格式

第 $1$ 行有 $1$ 个正整数 $n$,表示有 $n$ 件工作要分配给 $n$ 个人做。

接下来的 $n$ 行中,每行有 $n$ 个整数 $c_{ij}$,表示第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{ij}$。

输出格式

第一行输出最差分配方案下的最小总效益。

第二行输出最优分配方案下的最大总效益。

数据范围

$1 \le n \le 50$,
$0 \le c_{ij} \le 100$

输入样例:

5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1

输出样例:

5
14

解题思路

费用流,二分图最优匹配

建图:建立源点 $s$ 和汇点 $t$,$s$ 向所有工人表示的点连边,容量为 $1$,费用为 $0$,所有的工作表示的点向 $t$ 连边,容量为 $1$,费用为 $0$,所有的工人表示的点向所有工作表示的点连边,容量足够大,费用为工人对待工作的效益,最后 $s$ 到 $t$ 的费用流即为所求,$\color{red}{为什么?}$简单说一下,可行流与实际问题一一对应,即如果工人表示的点到某个工作表示的点有流量,则说明该工人选择该工作,且由于可行流流量守恒,最后一定是满流状态,即最大流,这时的费用流最小/大,对应实际问题中匹配的效益之和最小/大

  • 时间复杂度:$O(kn^2f)$

代码

// Problem: 分配问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2195/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=105,M=(N+2505)*2,inf=1e9;
int n,S,T;
int h[N],f[M],w[M],e[M],ne[M],idx;
int incf[N],d[N],pre[N],q[N];
bool st[N];
void add(int a,int b,int c,int d)
{
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa()
{
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    d[S]=0,incf[S]=inf,q[0]=S;
    int hh=0,tt=1;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N)hh=0;
        st[x]=false;
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]>d[x]+w[i]&&f[i])
            {
                d[y]=d[x]+w[i];
                pre[y]=i;
                incf[y]=min(incf[x],f[i]);
                if(!st[y])
                {
                    q[tt++]=y;
                    if(tt==N)tt=0;
                    st[y]=true;
                }
            }
        }
    }
    return incf[T]>0;
}
int EK()
{
    int cost=0;
    while(spfa())
    {
        int t=incf[T];
        cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1])f[pre[i]]-=t,f[pre[i]^1]+=t;
    }
    return cost;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    S=0,T=n*2+1;
    for(int i=1;i<=n;i++)
        add(S,i,1,0),add(i+n,T,1,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            int c;
            scanf("%d",&c);
            add(i,j+n,inf,c);
        }
    printf("%d\n",EK());
    for(int i=0;i<idx;i+=2)
    {
        f[i]+=f[i^1],f[i^1]=0;
        swap(w[i],w[i^1]);
    }
    printf("%d",-EK());
    return 0;
}



acwing_zyy
12小时前

题目链接

2194. 负载平衡问题

$G$ 公司有 $n$ 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。

如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。

搬运货物时,只能在相邻的仓库之间搬运。

数据保证一定有解。

输入格式

第 $1$ 行中有 $1$ 个正整数 $n$,表示有 $n$ 个仓库。

第 $2$ 行中有 $n$ 个正整数,表示 $n$ 个仓库的库存量。

输出格式

输出最少搬运量。

数据范围

$1 \le n \le 100$,
每个仓库的库存量不超过 $100$。

输入样例:

5
17 9 14 16 4

输出样例:

11

解题思路

费用流

本题类似于 2192. 运输问题(即将超出平均值的点当作仓库,少于平均值的点当作商店)
建图:求出平均值 $x$,建立源点 $s$ 和汇点 $t$,对于超出平均值的部分的点,$s$ 向其连边,容量为超出平均值的部分,费用为 $0$,另外其需要向相邻两点连边,容量足够大,费用为 $1$,所有少于平均值的部分的点向 $t$ 连边,容量为少于平均值的部分,费用为 $0$,不难发现:可行流与实际问题一一对应,满流时即所有数都变为平均值的时候,且达到最大流时费用最少即移动的代价最少

  • 时间复杂度:$(knf)$

贪心

本题同 122. 糖果传递

  • 时间复杂度:$O(n)$

代码

  • 费用流
// Problem: 负载平衡问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2196/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=105,M=N*6,inf=1e9;
int n,a[N],S,T;
int h[N],e[M],w[M],f[M],ne[M],idx;
int incf[N],d[N],pre[N],q[N];
bool st[N];
void add(int a,int b,int c,int d)
{
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa()
{
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    d[S]=0,incf[S]=inf,q[0]=S;
    int hh=0,tt=1;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N)hh=0;
        st[x]=false;
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]>d[x]+w[i]&&f[i])
            {
                d[y]=d[x]+w[i];
                pre[y]=i;
                incf[y]=min(incf[x],f[i]);
                if(!st[y])
                {
                    q[tt++]=y;
                    if(tt==N)tt=0;
                    st[y]=true;
                }
            }
        }
    }
    return incf[T]>0;
}
int EK()
{
    int cost=0;
    while(spfa())
    {
        int t=incf[T];
        cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1])f[pre[i]]-=t,f[pre[i]^1]+=t;
    }
    return cost;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    int s=0;
    S=0,T=n+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s+=a[i];
    }
    s/=n;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>s)add(S,i,a[i]-s,0);
        else if(a[i]<s)add(i,T,s-a[i],0);
        add(i,i<n?i+1:1,inf,1);
        add(i,i>1?i-1:n,inf,1);
    }
    printf("%d",EK());
    return 0;
}
  • 贪心
// Problem: 负载平衡问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2196/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=105;
int n,a[N],b[N];
int main()
{
    scanf("%d",&n);
    int s=0,avg=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s+=a[i];
    }
    avg=s/n;
    for(int i=2;i<=n;i++)b[i]=b[i-1]+a[i]-avg;
    nth_element(b+1,b+(n+1)/2,b+1+n);
    int res=0;
    for(int i=1;i<=n;i++)
        res+=abs(b[i]-b[(n+1)/2]);
    printf("%d",res);
    return 0;
}



acwing_zyy
13小时前

题目链接

2192. 运输问题

$W$ 公司有 $m$ 个仓库和 $n$ 个零售商店。

第 $i$ 个仓库有 $a_i$ 个单位的货物;第 $j$ 个零售商店需要 $b_j$ 个单位的货物。

货物供需平衡,即$\sum\limits_{i=1}^{m}a_i=\sum\limits_{j=1}^{n}b_j$。

从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用为 $c_{ij}$。

试设计一个将仓库中所有货物运送到零售商店的运输方案。

对于给定的 $m$ 个仓库和 $n$ 个零售商店间运送货物的费用,计算最优运输方案和最差运输方案。

输入格式

第 $1$ 行有 $2$ 个正整数 $m$ 和 $n$,分别表示仓库数和零售商店数。

接下来的一行中有 $m$ 个正整数 $a_i$,表示第 $i$ 个仓库有 $a_i$ 个单位的货物。

再接下来的一行中有 $n$ 个正整数 $b_j$,表示第 $j$ 个零售商店需要 $b_j$ 个单位的货物。

接下来的 $m$ 行,每行有 $n$ 个整数,表示从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用 $c_{ij}$。

输出格式

第一行输出最少运输费用。

第二行输出最多运输费用。

数据范围

$1 \le m \le 100$,
$1 \le n \le 50$,
$1 \le a_i \le 30000$,
$1 \le b_i \le 60000$,
$1 \le c_{ij} \le 1000$

输入样例:

2 3
220 280
170 120 210
77 39 105
150 186 122

输出样例:

48500
69140

解题思路

费用流

建图:建立源点 $s$ 和汇点 $t$,源点向仓库连边,容量为仓库库存,费用为 $0$,所有商店向汇点连边,容量为商店需求,费用为 $0$,所有仓库向商店连边,容量足够大,费用为从商店将货物移到该商店的单价,最后求解从 $s$ 到 $t$ 的费用流即为所求,$\color{red}{为什么?}$不能发现,最后一定是满流的状态,从仓库流到商店的流量表示向该商店出多少货,费用即为单价乘以流的量,可行流和实际问题是一一对应的

设最大流为 $f$,$k$ 为 spfa 算法常数,则:

  • 时间复杂度:$O(knmf)$

代码

// Problem: 运输问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2194/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=155,M=(5005+N)*2,inf=1e9;
int m,n,S,T;
int h[N],e[M],ne[M],f[M],w[M],idx;
int d[N],incf[N],q[N],pre[N];
bool st[N];
void add(int a,int b,int c,int d)
{
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa()
{
    int hh=0,tt=1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S,d[S]=0,incf[S]=inf;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N)hh=0;
        st[x]=false;
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]>d[x]+w[i]&&f[i])
            {
                d[y]=d[x]+w[i];
                pre[y]=i;
                incf[y]=min(incf[x],f[i]);
                if(!st[y])
                {
                    q[tt++]=y;
                    if(tt==N)tt=0;
                    st[y]=true;
                }
            }
        }
    }
    return incf[T]>0;
}
int EK()
{
    int cost=0;
    while(spfa())
    {
        int t=incf[T];
        cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1])
            f[pre[i]]-=t,f[pre[i]^1]+=t;
    }
    return cost;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    S=0,T=m+n+1;
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a);
        add(S,i,a,0);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b);
        add(i+m,T,b,0);
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&c);
            add(i,j+m,inf,c);
        }
    printf("%d\n",EK());
    for(int i=0;i<idx;i+=2)
    {
        f[i]+=f[i^1],f[i^1]=0;
        swap(w[i],w[i^1]);
    }
    printf("%d",-EK());
    return 0;
}



acwing_zyy
13小时前

题目链接

2174. 费用流

给定一个包含 $n$ 个点 $m$ 条边的有向图,并给定每条边的容量和费用,边的容量非负。

图中可能存在重边和自环,保证费用不会存在负环。

求从 $S$ 到 $T$ 的最大流,以及在流量最大时的最小费用。

输入格式

第一行包含四个整数 $n,m,S,T$。

接下来 $m$ 行,每行三个整数 $u,v,c,w$,表示从点 $u$ 到点 $v$ 存在一条有向边,容量为 $c$,费用为 $w$。

点的编号从 $1$ 到 $n$。

输出格式

输出点 $S$ 到点 $T$ 的最大流和流量最大时的最小费用。

如果从点 $S$ 无法到达点 $T$ 则输出 0 0

数据范围

$2≤n≤5000$,
$1≤m≤50000$,
$0≤c≤100$,
$-100 \le w \le 100$
$S≠T$

输入样例:

5 5 1 5
1 4 10 5
4 5 5 10
4 2 12 5
2 5 10 15
1 5 10 10

输出样例:

20 300

解题思路

费用流

引入费用流时流网络中的边不止有流量的概念,还得有费用的概念
费用流即最小/大费用最大流(即最大可行流中的最小/大费用)的简称
费用流:$最大流时每条边上的可行流\times 该边上的费用$
EK 算法改进的费用流算法比较常见,这里主要讨论这个改进后的算法
主要是将 EK 算法中的 bfs 改为 spfaspfa 用来求解源点 $s$ 到 $t$ 的最短/长路(即 $s$ 到 $t$ 上的最小路径费用和)在求最短/长路的同时找到一条增广路径,然后增加这部分的费用,直到找不到增广路径为止,$\color{red}{为什么这样可以求解费用流}$,假设对于当前可行流 $f_1$,$f_1$ 是费用最小的,假设在 $f_1$ 的残余网络中经过 spfa 找到一条增广路径,即可行流 $f_2$,则可知 $f=f_1+f_2$ 仍是一个可行流,假设此时 $f$ 虽然是当前为止费用并非最小的可行流,即有这样一个可行流 $f’=f_1+f_2’$,其中 $|f|=|f’|$,但是 $f’$ 的费用要比 $f$ 小,注意,此时有 $|f_2|=|f_2’|$,设 $cost(f)$ 为 $f$ 这个可行流的费用,则 $cost(f’)=cost(f_1)+cost(f_2’)=cost(f_1)+|f_2’|\times dist(f_2’))<cost(f)=cost(f_1)+cost(f_2)=cost(f_1)+|f_2|\times dist(f_2)$,则有 $dist(f_2’)<dist(f_2)$,由于 $dist(f_2)$ 已经是最短路了,故假设不成立,故这种方法正确

设最大流为 $f$,$k$ 为 spfa 算法的常数,则:

  • 时间复杂度:$O(kmf)$

类似的,也有 dinic 算法的改进版

  • 时间复杂度:$O(kmf)$

代码

  • EK 算法改进
// Problem: 费用流
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2176/
// Memory Limit: 64 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5005,M=100005,inf=1e9;
int n,m,S,T;
int h[N],ne[M],f[M],w[M],e[M],idx;
int incf[N],d[N],q[N],pre[N];
bool st[N];
void add(int a,int b,int c,int d)
{
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa()
{
    int hh=0,tt=1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S,d[S]=0,incf[S]=inf;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N)hh=0;
        st[x]=false;
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]>d[x]+w[i]&&f[i])
            {
                d[y]=d[x]+w[i];
                pre[y]=i;
                incf[y]=min(incf[x],f[i]);
                if(!st[y])
                {
                    q[tt++]=y;
                    if(tt==N)tt=0;
                    st[y]=true;
                }
            }
        }
    }
    return incf[T]>0;
}
void EK(int &flow,int &cost)
{
    flow=cost=0;
    while(spfa())
    {
        int t=incf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1])
        {
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }

    }
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
    }
    int flow,cost;
    EK(flow,cost);
    printf("%d %d",flow,cost);
    return 0;
}
  • dinic 算法改进
// Problem: 费用流
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2176/
// Memory Limit: 64 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5005,M=100005,inf=1e9;
int n,m,S,T;
int h[N],ne[M],f[M],w[M],e[M],idx;
int incf[N],d[N],q[N],cur[N];
bool st[N];
void add(int a,int b,int c,int d)
{
    e[idx]=b,f[idx]=c,w[idx]=d,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,w[idx]=-d,ne[idx]=h[b],h[b]=idx++;
}
bool spfa()
{
    for(int i=1;i<=n;i++)cur[i]=h[i],d[i]=inf,incf[i]=0;
    d[S]=0,incf[S]=inf;
    q[0]=S;
    int hh=0,tt=1;
    while(hh!=tt)
    {
        int x=q[hh++];
        if(hh==N)hh=0;
        st[x]=false;
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]>d[x]+w[i]&&f[i])
            {
                d[y]=d[x]+w[i];
                incf[y]=min(incf[x],f[i]);
                if(!st[y])
                {
                    q[tt++]=y;
                    if(tt==N)tt=0;
                    st[y]=true;
                }
            }
        }
    }
    return incf[T]>0;
}
int dfs(int x,int limit,int &cost)
{
    if(x==T)
    {
        cost+=d[T]*limit;
        return limit;
    }
    st[x]=true;
    int flow=0;
    for(int i=cur[x];~i&&flow<limit;i=ne[i])
    {
        int y=e[i];
        if(d[y]==d[x]+w[i]&&f[i]&&!st[y])
        {
            int t=dfs(y,min(f[i],limit-flow),cost);
            if(!t)d[y]=inf;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    st[x]=false;
    return flow;
}
void dinic(int &max_flow,int &cost)
{
    max_flow=cost=0;
    int flow=0;
    while(spfa())while(flow=dfs(S,inf,cost))max_flow+=flow;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
    }
    int flow,cost;
    dinic(flow,cost);
    printf("%d %d",flow,cost);
    return 0;
}



acwing_zyy
22小时前

题目链接

2199. 骑士共存问题

在一个 $n*n$ 个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。

棋盘上某些方格设置了障碍,骑士不得进入。

image

对于给定的 $n*n$ 个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击。

输入格式

第一行有 $2$ 个正整数 $n$ 和 $m$,分别表示棋盘的大小和障碍数。

接下来的 $m$ 行给出障碍的位置。每行 $2$ 个正整数,表示障碍的方格坐标。

输出格式

输出可以共存的最大骑士数量。

数据范围

$1 \le n \le 200$,
$0 \le m < n^2$

输入样例:

3 2
1 1
3 3

输出样例:

5

解题思路

二分图最大独立集,最大权独立集,最小割,二分图

378. 骑士放置,但本题用匈牙利算法会超时,得转化为用最小割求解的最大权独立集求解,本题也类似于 2326. 王者之剑

另外,需要注意:dinic 算法求解二分图复杂度为 $O(m\sqrt{n})$

  • 时间复杂度:$O(n^3)$

代码

// Problem: 骑士共存问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2200/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=205*205,M=N*8*2,inf=1e9;
int n,m,S,T;
bool g[205][205];
int dx[]={-1,-2,-2,-1,1,2,2,1},dy[]={-2,-1,1,2,-2,-1,1,2};
int h[N],f[M],ne[M],e[M],idx;
int d[N],hh,tt,q[N],cur[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
int get(int x,int y)
{
    return (x-1)*n+y;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=hh=tt=0;
    q[0]=S;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]==-1&&f[i])
            {
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++tt]=y;
            }
        }
    }
    return false;
}
int dfs(int x,int limit)
{
    if(x==T)return limit;
    int flow=0;
    for(int i=cur[x];~i&&flow<limit;i=ne[i])
    {
        cur[x]=i;
        int y=e[i];
        if(d[y]==d[x]+1&&f[i])
        {
            int t=dfs(y,min(f[i],limit-flow));
            if(!t)d[y]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int res=0,flow;
    while(bfs())while(flow=dfs(S,inf))res+=flow;
    return res;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    S=0,T=n*n+1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x][y]=true;
    }
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(g[i][j])continue;
            res++;
            if((i+j)%2)
            {
                add(S,get(i,j),1);
                for(int k=0;k<8;k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    if(x<1||x>n||y<1||y>n||g[x][y])continue;
                    add(get(i,j),get(x,y),inf);
                }
            }
            else
                add(get(i,j),T,1);
        }
    printf("%d",res-dinic());
    return 0;
}


活动打卡代码 AcWing 2199. 骑士共存问题

acwing_zyy
22小时前
// Problem: 骑士共存问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2200/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=205*205,M=N*8*2,inf=1e9;
int n,m,S,T;
bool g[205][205];
int dx[]={-1,-2,-2,-1,1,2,2,1},dy[]={-2,-1,1,2,-2,-1,1,2};
int h[N],f[M],ne[M],e[M],idx;
int d[N],hh,tt,q[N],cur[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
int get(int x,int y)
{
    return (x-1)*n+y;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=hh=tt=0;
    q[0]=S;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]==-1&&f[i])
            {
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++tt]=y;
            }
        }
    }
    return false;
}
int dfs(int x,int limit)
{
    if(x==T)return limit;
    int flow=0;
    for(int i=cur[x];~i&&flow<limit;i=ne[i])
    {
        cur[x]=i;
        int y=e[i];
        if(d[y]==d[x]+1&&f[i])
        {
            int t=dfs(y,min(f[i],limit-flow));
            if(!t)d[y]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int res=0,flow;
    while(bfs())while(flow=dfs(S,inf))res+=flow;
    return res;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    S=0,T=n*n+1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x][y]=true;
    }
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(g[i][j])continue;
            res++;
            if((i+j)%2)
            {
                add(S,get(i,j),1);
                for(int k=0;k<8;k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    if(x<1||x>n||y<1||y>n||g[x][y])continue;
                    add(get(i,j),get(x,y),inf);
                }
            }
            else
                add(get(i,j),T,1);
        }
    printf("%d",res-dinic());
    return 0;
}



acwing_zyy
23小时前

题目链接

2176. 太空飞行计划问题

$W$ 教授正在为国家航天中心计划一系列的太空飞行。

每次太空飞行可进行一系列商业性实验而获取利润。

现已确定了一个可供选择的实验集合 $E={E_1,E_2,\dots,E_m}$ 和进行这些实验需要使用的全部仪器的集合 $I={I_1,I_2,\dots,I_n}$。

实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j \subseteq I$。

配置仪器 $I_k$ 的费用为 $c_k$ 美元。

实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。

$W$ 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。

这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

输入格式

第 $1$ 行有 $2$ 个正整数 $m$ 和 $n$。$m$ 是实验数,$n$ 是仪器数。

接下来的 $m$ 行,每行是一个实验的有关数据。

第一个数赞助商同意支付该实验的费用;接着是该实验需要用到的若干仪器的编号。

最后一行的 $n$ 个数是配置每个仪器的费用。

实验和仪器的编号都是从 $1$ 开始。

输出格式

将最佳实验方案输出。

第 $1$ 行是实验编号;

第 $2$ 行是仪器编号;

最后一行是净收益。

如果最佳方案不唯一,则输出任意一种均可。

数据范围

$1 \le m,n \le 50$,
所有仪器费用以及赞助费用均不超过 $100$。

输入样例:

2 3
10 1 2
25 2 3
5 6 7

输出样例:

1 2
1 2 3
17

解题思路

最小割

一个点向其他点连边,如果该点要选的话则其连边的也必须要选,即最大权闭合图模板题,具体见 961. 最大获利
另外,还需要输出方案,$S-{s}$ 即为闭合子图,dfs 出 $S$ 部分即可

  • 时间复杂度:$O((n+m)^2\times nm)$

代码

// Problem: 太空飞行计划问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2178/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=105,M=(N+2505)*2,inf=1e9;
int m,n,S,T;
int h[N],f[M],ne[M],e[M],idx;
int d[N],hh,tt,q[N],cur[N];
bool v[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=hh=tt=0;
    q[0]=S;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]==-1&&f[i])
            {
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++tt]=y;
            }
        }
    }
    return false;
}
int dfs(int x,int limit)
{
    if(x==T)return limit;
    int flow=0;
    for(int i=cur[x];~i&&flow<limit;i=ne[i])
    {
        cur[x]=i;
        int y=e[i];
        if(d[y]==d[x]+1&&f[i])
        {
            int t=dfs(y,min(f[i],limit-flow));
            if(!t)d[y]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }

    }
    return flow;
}
int dinic()
{
    int res=0,flow;
    while(bfs())while(flow=dfs(S,inf))res+=flow;
    return res;
}
void dfs(int x)
{
    v[x]=true;
    for(int i=h[x];~i;i=ne[i])
        if(f[i]&&!v[e[i]])dfs(e[i]);
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    getchar();
    S=0,T=n+m+1;
    string s;
    int x,tot=0;
    for(int i=1;i<=m;i++)
    {
        getline(cin,s);
        stringstream sin(s);
        sin>>x;
        add(S,i,x);
        tot+=x;
        while(sin>>x)add(i,x+m,inf);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i+m,T,x);
    }
    int res=dinic();
    dfs(S);
    for(int i=1;i<=m;i++)
        if(v[i])printf("%d ",i);
    puts("");
    for(int i=1;i<=n;i++)
        if(v[i+m])printf("%d ",i);
    puts("");
    printf("%d",tot-res);
    return 0;
}



acwing_zyy
23小时前
// Problem: 太空飞行计划问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2178/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=105,M=(N+2505)*2,inf=1e9;
int m,n,S,T;
int h[N],f[M],ne[M],e[M],idx;
int d[N],hh,tt,q[N],cur[N];
bool v[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=hh=tt=0;
    q[0]=S;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]==-1&&f[i])
            {
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++tt]=y;
            }
        }
    }
    return false;
}
int dfs(int x,int limit)
{
    if(x==T)return limit;
    int flow=0;
    for(int i=cur[x];~i&&flow<limit;i=ne[i])
    {
        cur[x]=i;
        int y=e[i];
        if(d[y]==d[x]+1&&f[i])
        {
            int t=dfs(y,min(f[i],limit-flow));
            if(!t)d[y]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }

    }
    return flow;
}
int dinic()
{
    int res=0,flow;
    while(bfs())while(flow=dfs(S,inf))res+=flow;
    return res;
}
void dfs(int x)
{
    v[x]=true;
    for(int i=h[x];~i;i=ne[i])
        if(f[i]&&!v[e[i]])dfs(e[i]);
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    getchar();
    S=0,T=n+m+1;
    string s;
    int x,tot=0;
    for(int i=1;i<=m;i++)
    {
        getline(cin,s);
        stringstream sin(s);
        sin>>x;
        add(S,i,x);
        tot+=x;
        while(sin>>x)add(i,x+m,inf);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i+m,T,x);
    }
    int res=dinic();
    dfs(S);
    for(int i=1;i<=m;i++)
        if(v[i])printf("%d ",i);
    puts("");
    for(int i=1;i<=n;i++)
        if(v[i+m])printf("%d ",i);
    puts("");
    printf("%d",tot-res);
    return 0;
}



题目链接

381. 有线电视网络

给定一张 $n$ 个点 $m$ 条边的无向图,求最少去掉多少个点,可以使图不连通。

如果不管去掉多少个点,都无法使原图不连通,则直接返回 $n$。

输入格式

输入包含多组测试数据。

每组数据占一行,首先包含两个整数 $n$ 和 $m$,接下来包含 $m$ 对形如 $(x,y)$ 的数对,形容点 $x$ 与点 $y$ 之间有一条边。

数对 $(x,y)$ 中间不会包含空格,其余地方用一个空格隔开。

输出格式

每组数据输出一个结果,每个结果占一行。

数据范围

$0 \le n \le 50$

输入样例:

0 0
1 0
3 3 (0,1) (0,2) (1,2)
2 0
5 7 (0,1) (0,2) (1,3) (1,2) (1,4) (2,3) (3,4)

输出样例:

0
1
3
0
2

解题思路

最小割

建图:因为如果不连通的话最后必定有两点不连通,不妨将这两个点作为源点和汇点,即枚举源点 $s$ 和汇点 $t$,如果是要删除边使图不连通,则很显然删除割边即可,即最小割即为答案,但这里要求删除点,不妨考虑拆点,将所有点拆分为入点和出点,在流网络中入点向出点连一条容量为 $1$ 的边,其他边容量足够大,由最小割要求的是最小的割,或者最大流最小割定理,由于跑最大流是一定要经过点,而点的容量是有限的,即最大流一定是有限的,即最小割有限,最后的割边就相当于是点。另外还有一个优化:不用枚举源点或汇点,即将其中一个固定,$\color{red}{为什么?}$由于固定的点一定在 $S$ 或者 $T$ 中,假设在 $S$ 中,则由于是无向图,即对应流网络中除去入点和出点之间的边其余正边和反边的容量都是足够大,将 $s$ 和固定点交换得到的结果还是一样的(不妨想象成所有的流量逆行)

  • 时间复杂度:$O(n^5)$

代码

// Problem: 有线电视网络
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/383/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>

//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=105,M=(55+2500)*2,inf=1e9;
int n,m,S,T;
int h[N],f[M],ne[M],e[M],idx;
int d[N],hh,tt,q[N],cur[N];
void add(int a,int b,int c)
{
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
    memset(d,-1,sizeof d);
    d[S]=hh=tt=0;
    q[0]=S;
    cur[S]=h[S];
    while(hh<=tt)
    {
        int x=q[hh++];
        for(int i=h[x];~i;i=ne[i])
        {
            int y=e[i];
            if(d[y]==-1&&f[i])
            {
                d[y]=d[x]+1;
                cur[y]=h[y];
                if(y==T)return true;
                q[++tt]=y;
            }
        }
    }
    return false;
}
int dfs(int x,int limit)
{
    if(x==T)return limit;
    int flow=0;
    for(int i=cur[x];~i&&flow<limit;i=ne[i])
    {
        cur[x]=i;
        int y=e[i];
        if(d[y]==d[x]+1&&f[i])
        {
            int t=dfs(y,min(f[i],limit-flow));
            if(!t)d[y]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
int dinic()
{
    int res=0,flow;
    while(bfs())while(flow=dfs(S,inf))res+=flow;
    return res;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=1;i<=n;i++)add(i,i+n,1);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf(" (%d,%d)",&x,&y);
            x++,y++;
            add(x+n,y,inf),add(y+n,x,inf);
        }
        int res=n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<i;j++)
            {
                S=i+n,T=j;
                for(int i=0;i<idx;i+=2)f[i]+=f[i^1],f[i^1]=0;
                res=min(res,dinic());
            }
        printf("%d\n",res);
    }
    return 0;
}