P8215 [THUPC2022 初赛] 分组作业 题解

· · 题解

做法

最小割。

这是我第一次在赛场上做出有难度的网络流，写篇题解纪念一下。

赛后发现我的建模方法和官方题解并不相同，所以这篇题解也算是提供了一种新奇的建图思路吧。

首先观察到每个人有两种选择：愿意和不愿意。那么可以用源点表示愿意，汇点表示不愿意。具体就是对第 i 个人建立节点 i，然后从源点向 i 连一条流量为 d_i 的边，从 i 向汇点连一条流量为 c_i 的边：

然后考虑同一组内的两个人 x,y 意见不同（x 选择了愿意）的情况，此时情况如下：

因为会产生 e_x 的不满，所以从 x 向 y 连一条流量为 e_x 的边来增加不满。

对于 y 选择了愿意但是 x 选择了不愿意的情况亦然。

加上这些边之后的图如下：（两个奇奇怪怪的点是用来防止边权重叠的）

接下来我们就需要解决最棘手的喜欢关系了。（赛场上想了 1h 左右/ll）

首先可以发现，只有一组里两个人都选择愿意才可以合作。所以可以给每一组引入一个点 x_i，从 x_i 分别向两个成员连流量为 \inf 的边：

这么连边的目的是，假设有一些流量送到了 x_i：

那么就可以保证每一组如果不合作的话给 x_i 送流量的边都要被割断，如果合作的话就不隔断，并且如果一组中有一个或以上人选择了不愿意那么就必须不合作。换句话说，x_i 没有流量代表这一组不合作，否则代表这一组合作。

现在我们可以表示合不合作了，接下来考虑喜欢关系的连边。

若第 j 组关系是 x_j 喜欢 y_j，设 u 表示 x_j 那一组的 x_i，v 表示 y_j 那一组的 x_i，那么：

如果 x_j 没有和队友合作，并且 y_j 选择了愿意，在图上就是 y_j 有流量并且 u 不能有流量。此时会产生 a_j 的不满，那么我们可以从有流量的 y_j 向不能有流量的 u 连一条流量为 a_j 的边。

如果 x_j 选择了不愿意，并且 y_j 和队友合作了，在图上就是 x_j 连向汇点的边没有被割断并且 v 有流量。此时会产生 b_j 的不满，那么我们可以从有流量的 v 向可以到达汇点的 x_j 连一条流量为 b_j 的边。

加上这些边后的图：（假设有一条喜欢关系：2 喜欢 3）

这样我们就建完图了，跑最小割即可。

AC 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

struct node
{
};

typedef long long ll;

const ll S=5000005,MS=1000005;

int n,m,s,t;
int xid[MS];
int esum,to[S],nxt[S],h[MS];
ll c[S];
int dep[MS];

inline void init()
{
    esum=1;
    memset(h,0,sizeof(h));
    s=0;
    t=1000003;
}

inline void add(int x,int y,ll w)
{
    c[++esum]=w;
    to[esum]=y;
    nxt[esum]=h[x];
    h[x]=esum;
}

inline bool bfs()
{
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(s);
    dep[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=nxt[i])
        {
            int v=to[i];
            if(c[i]>0&&dep[v]==0)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]!=0;
}

ll dfs(int u,ll w)
{
    if(u==t)
    {
        return w;
    }
    ll sum=0;
    for(int i=h[u];i;i=nxt[i])
    {
        int v=to[i];
        if(c[i]>0&&dep[v]==dep[u]+1)
        {
            ll re=dfs(v,min(w,c[i]));
            c[i]-=re;
            c[i^1]+=re;
            sum+=re;
            w-=re;
            if(w==0)
            {
                break;
            }
        }
    }
    if(sum==0)
    {
        dep[u]=0;
    }
    return sum;
}

inline ll dinic()
{
    ll ans=0;
    while(bfs())
    {
        ans+=dfs(s,1e17);
    }
    return ans;
}

inline void slove()
{
    scanf("%d%d",&n,&m);
    n*=2;
    init();
    for(int i=1;i<=n;i++)
    {
        ll C,D,E;
        scanf("%lld%lld%lld",&C,&D,&E);
        add(s,i,D);
        add(i,s,0);
        add(i,t,C);
        add(t,i,0);
        int v=(i&1)?i+1:i-1;
        add(i,v,E);
        add(v,i,0);
    }
    for(int i=1;i<=n;i+=2)
    {
        int u=n+(i+1)/2;
        add(u,i,1e17);
        add(i,u,0);
        add(u,i+1,1e17);
        add(i+1,u,0);
        xid[i]=u;
        xid[i+1]=u;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        ll a,b;
        scanf("%d%d%lld%lld",&x,&y,&a,&b);
        int u1=xid[y],v1=xid[x];
        add(u1,x,b);
        add(x,u1,0);
        add(y,v1,a);
        add(v1,y,0);
    }
    printf("%lld\n",dinic());
}

int main()
{
    int _=1;
//  scanf("%d",&_);
    while(_--)
    {
        slove();
    }
    return 0; 
}