2 条题解

  • 0
    @ 2025-4-27 1:42:36

    题意分析

    本题是一个资源分配优化问题，核心在于根据猪圈数量、初始猪数量、顾客拥有的猪圈钥匙情况以及顾客购买需求，合理分配猪，使当天卖出猪的总数最大。

    解题思路

    1. 构建网络流模型
      • 源点和汇点：设置源点 0 和汇点 N + 1 。源点 0 与每个猪圈相连，边的容量为对应猪圈初始猪的数量，因为源点代表猪的初始供应。每个顾客与汇点相连，边的容量为顾客希望购买猪的数量，即顾客的需求上限。
      • 猪圈与顾客的连接：若顾客拥有某个猪圈的钥匙，就建立从该猪圈对应的编号到顾客编号的边，容量设为无穷大（用 INF 表示）。这是因为顾客打开猪圈后，理论上可从该猪圈获取任意数量猪（只要猪圈有猪）。
      • 猪圈之间的连接：对于同一个猪圈，按顾客到来顺序，连接相邻顾客对应的编号，容量为无穷大。这是因为在顾客离开前，Mirko 可在解锁的猪圈中重新分配剩余的猪，即前一个顾客打开猪圈后剩余的猪可用于满足后一个顾客需求。
    2. 使用 Dinic 算法求解最大流
      • BFS 分层：bfs 函数通过广度优先搜索为图中每个顶点分层，构建层次图。从源点 0 开始，给每个可达顶点标记层次，用于后续 dfs 寻找增广路径时判断路径是否合法（必须是从层次小的顶点到层次大1的顶点）。
      • DFS 增广：dfs 函数在层次图上进行深度优先搜索，寻找增广路径并增广流量。在搜索过程中，沿着层次合法的边进行探索，一旦找到汇点，就确定了一条增广路径，更新路径上的边的容量（正向边减流量，反向边加流量），并返回增广的流量值。
      • 重复求解：在 Dinic 函数中，不断调用 bfs 和 dfs 。每次 bfs 构建新的层次图，然后 dfs 在该层次图上寻找增广路径并增广，直到 bfs 无法到达汇点（即不存在增广路径），此时的流量总和就是最大流，也就是 Mirko 最多能卖出猪的数量。

    代码详解

    1

    #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f
 
using namespace std;
 
int M,N;
vector<int> que[1010];
int pig[1010];
int cus[110];
const int maxe=1e4+1000;
const int maxv=110;
struct edge
{
    int to,w,next;
}e[maxe<<1];
int head[maxv<<1],depth[maxv],cnt;
void init()
{
    memset(head,-1,sizeof(head));
    cnt=-1;
}
void add_edge(int u,int v,int w)
{
    e[++cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void _add(int u,int v,int w)
{
    add_edge(u,v,w);
    add_edge(v,u,0);
}
void get_map()
{
    init();
    for(int i=1;i<=M;i++)
        _add(0,que[i][0],pig[i]);
    for(int i=1;i<=N;i++)
        _add(i,N+1,cus[i]);
    for(int i=1;i<=M;i++)
        for(int j=0;j<que[i].size()-1;j++)
            _add(que[i][j],que[i][j+1],INF);
}
 
bool bfs()
{
    queue<int> q;
    while(!q.empty()) q.pop();
    memset(depth,0,sizeof(depth));
    depth[0]=1;
    q.push(0);
 
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            if(!depth[e[i].to] && e[i].w>0)
            {
                depth[e[i].to]=depth[u]+1;
                q.push(e[i].to);
            }
        }
    }
    if(!depth[N+1]) return false;
    return true;
}
int dfs(int u,int flow)
{
    if(u==N+1) return flow;
    int ret=0;
    for(int i=head[u];i!=-1 && flow;i=e[i].next)
    {
        if(depth[u]+1==depth[e[i].to] && e[i].w!=0)
        {
            int tmp=dfs(e[i].to,min(e[i].w,flow));
            if(tmp>0)
            {
                flow-=tmp;
                ret+=tmp;
                e[i].w-=tmp;
                e[i^1].w+=tmp;
            }
        }
    }
    return ret;
}
void Dinic()
{
    int ans=0;
    while(bfs())
    {
        ans+=dfs(0,INF);
    }
    cout<<ans<<endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>M>>N)
    {
        memset(pig,0,sizeof(pig));
        for(int i=0;i<1010;i++) que[i].clear();
        memset(cus,0,sizeof(cus));
        for(int i=1;i<=M;i++)
            cin>>pig[i];
        for(int i=1;i<=N;i++)
        {
            int k;
            cin>>k;
            while(k--)
            {
                int num;
                cin>>num;
                que[num].push_back(i);
            }
            cin>>cus[i];
        }
        get_map();
        Dinic();
    }
    return 0;
}

    复杂度分析

    1. 时间复杂度：Dinic 算法的时间复杂度为 \(O(V^2E)\) ，其中 \(V\) 是顶点数，\(E\) 是边数。在本题中，顶点数 \(V = M + N + 2\)（\(M\) 个猪圈，\(N\) 个顾客，加上源点和汇点） ，边数 \(E\) 数量级为 \(O(MN + M + N)\) ，所以整体时间复杂度为 \(O((M + N + 2)^2(MN + M + N))\) 。在实际数据规模下，该算法能较快求解。
    2. 空间复杂度：主要用于存储图的邻接表、顶点层次数组等。邻接表存储边需要 \(O(E)\) 空间，顶点层次数组等辅助空间为 \(O(V)\) ，所以空间复杂度为 (O(V + E)=O(M + N + MN + M + N)=O(MN + M + N)) 。
    • 0
      @ 2025-4-6 18:24:39

      🧠 题解（Solution）

      ✅ 问题抽象：

      本题可以看成是一个**最大流模型（Maximum Flow）**问题，关键在于建图方式。

      🔍 状态建模：最大流图构建 我们构造一个流网络如下：

      源点 SS 和 汇点 TT；

      每个顾客 CiC_i 作为中间结点；

      每个顾客拥有的猪圈集合视为**“资源池”**；

      由于在访问后，猪可以在解锁猪圈之间重新分配，因此，共享猪资源的顾客可以互相转移“剩余猪只”；

      利用并查集（Disjoint Set）或 记录猪圈已由哪个顾客访问首次打开来建立顾客之间的连接边。

      ✅ 网络图构建逻辑：

      源点 SS 向所有“首次访问某猪圈”的顾客 CiC_i 连边，容量为该猪圈初始猪数；

      所有顾客 CiC_i 向汇点 TT 连边，容量为该顾客的购买需求 BiB_i；

      若两个顾客 CiC_i 和 CjC_j 访问了相同的猪圈，则在 CiC_i 与 CjC_j 之间连一条容量为无穷大的边，表示可以转移猪。

      🧮 示例分析（输入数据 1）： 初始猪圈：[3,1,10][3, 1, 10]

      顾客：

      C1C_1：钥匙 1,2{1, 2}，想买 22；

      C2C_2：钥匙 1,3{1, 3}，想买 33；

      C3C_3：钥匙 2{2}，想买 66；

      网络构造： S→C1S \rightarrow C_1：容量 3+1=43 + 1 = 4

      S→C2S \rightarrow C_2：容量 1010

      C1→C3C_1 \rightarrow C_3：因为猪圈 22 是共享的，连边容量无穷

      C1→C2C_1 \rightarrow C_2：因为猪圈 11 是共享的，连边容量无穷

      C1→TC_1 \rightarrow T：容量 22

      C2→TC_2 \rightarrow T：容量 33

      C3→TC_3 \rightarrow T：容量 66

      最大流求解后，输出即为最大可售猪数：77

      ⚙️ 可用算法： Dinic 算法（推荐，复杂度 O(EV)O(E \sqrt{V})）；

      Edmonds-Karp（更易实现，但较慢）；

      代码实现：

      #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline char gc()
{
    static char now[1<<16],*S,*T;
    if(S==T) {T=(S=now)+fread(now,1,1<<16,stdin); if(S==T) return EOF;}
    return *S++;
}
inline int read()
{
    int x=0; char ch=gc();
    while(ch<'0'||'9'<ch) ch=gc();
    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();
    return x; 
}
int const NM=1e5+10;
int const INF=0x7FFFFFFF;
int n,m,s,t;
int k[1001];
int cnt,h[NM];
struct edge{int v,c,nxt;} ed[NM<<1];
void edAdd(int u,int v,int c)
{
    cnt++; ed[cnt].v=v,ed[cnt].c=c,ed[cnt].nxt=h[u],h[u]=cnt;
    cnt++; ed[cnt].v=u,ed[cnt].c=0,ed[cnt].nxt=h[v],h[v]=cnt;
}
int dpt[NM]; int q[NM],op,cl;
bool bfs()
{
    op=cl=0; memset(dpt,0,sizeof dpt);
    dpt[q[++cl]=s]=1;
    while(op<cl)
    {
        int u=q[++op]; if(u==t) break;
        for(int i=h[u];i;i=ed[i].nxt)
        {
            int v=ed[i].v,c=ed[i].c;
            if(dpt[v]==0 && c) dpt[q[++cl]=v]=dpt[u]+1;
        }
    }
    if(dpt[t]==0) return false;
    else return true;
}
int fill(int u,int in)
{
    if(u==t || in==0) return in;
    int out=0;
    for(int i=h[u];i;i=ed[i].nxt)
    {
        int v=ed[i].v,c=ed[i].c;
        if(dpt[v]!=dpt[u]+1 || !c) continue;
        int flow=fill(v,min(in-out,c));
        if(flow==0) dpt[v]=0;
        else out+=flow,ed[i].c-=flow,ed[i^1].c+=flow;
    }
    return out;
}
int main()
{
    m=read(); n=read(); s=0; t=n*m+n+1;
    cnt=1;
    for(int i=1;i<=m;i++) edAdd(0,i,read());
    for(int p=1;p<=n-1;p++)
    {
        int a=read();
        for(int i=1;i<=m;i++) edAdd((p-1)*m+i,p*m+i,INF);
        for(int i=1;i<=a;i++) k[i]=(p-1)*m+read(),edAdd(k[i],n*m+p,INF);
        for(int i=1;i<=a;i++)
            for(int j=1;j<=a;j++) edAdd(k[i],k[j]+m,INF);
        edAdd(n*m+p,t,read());
    }
    int a=read();
    for(int i=1;i<=a;i++) k[i]=(n-1)*m+read(),edAdd(k[i],n*m+n,INF);
    edAdd(n*m+n,t,read());
    int ans=0;
    while(bfs()) ans+=fill(s,INF);
    printf("%d\n",ans);
    return 0;
}
      • 1

      PIGS

      信息

      ID
      150
      时间
      1000ms
      内存
      256MiB
      难度
      10
      标签
      递交数
      11
      已通过
      1
      上传者
      1. 评测队列
      2. 服务状态
      3. 兼容模式
      4. 主题
      2. 黔ICP备2023002402号-2
      3. Worker 0, 46ms
      4. Powered by Hydro v4.19.1 Community, Modified by 33DAI