题意分析

题目描述了一个会议室布置问题，其中有多个电源插座和多个需要插入的设备。每个插座和设备都有特定的插头类型。某些设备的插头类型可能没有对应的插座，但可以通过适配器将一种插头类型转换为另一种类型。目标是计算无法插入的设备的最小数量。

关键点：

1. 插座和设备：每个插座和设备都有特定的插头类型。
2. 适配器：可以将一种插头类型转换为另一种类型，且适配器可以串联使用。
3. 目标：通过合理使用适配器，最大化可插入的设备数量，从而最小化无法插入的设备数量。

解题思路

这个问题可以建模为最大流问题，其中：

• 源点（Source）表示所有设备。
• 汇点（Sink）表示所有插座。
• 中间节点表示适配器的转换关系。

方法选择：Dinic 算法

1. 网络流模型：

   • 源点连接到所有设备，容量为 1（每个设备只能插入一次）。
   • 设备连接到对应的插座类型节点，容量为 1。
   • 插座类型节点通过适配器连接到其他插座类型节点，容量为无穷大（因为适配器可以无限使用）。
   • 插座类型节点连接到汇点，容量为 1（每个插座只能插入一个设备）。

2. 数学表达：

   • 设 $D$ 为设备集合，$R$ 为插座集合，$A$ 为适配器集合。
   • 构建有向图 $G = (V, E)$，其中：
     • $V = \{s\} \cup D \cup R \cup \{t\}$。
     • $E$ 包含：
       • $(s, d)$，容量为 1，$\forall d \in D$。
       • $(d, r)$，容量为 1，如果设备 $d$ 的插头类型为 $r$。
       • $(r_i, r_j)$，容量为 $\infty$，如果存在适配器从 $r_i$ 到 $r_j$。
       • $(r, t)$，容量为 1，$\forall r \in R$。
   • 最大流的值即为最多可以插入的设备数量，无法插入的设备数量为 $m - \text{maxflow}$。

解决代码

#include <iostream>
#include <stdio.h>
#include <map>
#include <queue>
#include <string>
#include <string.h>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=110;
map<string,int>rec,dev;
int dev_cnt=1,rec_cnt=101;
int n,m,k;

struct Edge {
    int to,cap,flow;
};

struct Dinic {
    int cnt,s,t;
    int head[6*maxn];
    int deep[6*maxn];
    int vis[6*maxn];
    int cur[6*maxn];
    int next[maxn*maxn*4];
    Edge edge[maxn*maxn*4];

    void addEdge(int u,int v,int w)
    {
        edge[cnt].to=v;
        edge[cnt].cap=w;
        edge[cnt].flow=0;
        next[cnt]=head[u];
        head[u]=cnt++;

        edge[cnt].to=u;
        edge[cnt].cap=0;
        edge[cnt].flow=0;
        next[cnt]=head[v];
        head[v]=cnt++;
    }

    void init()
    {
        memset(head,-1,sizeof(head));
        cnt=0;
        s=0;
        t=601;
    }

    bool bfs()
    {
        memset(vis,0,sizeof(vis));
        memset(deep,0,sizeof(deep));
        deep[s]=0;
        vis[s]=1;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u=q.front();
            q.pop();
            for (int i=head[u];i!=-1;i=next[i]) {
                Edge &e=edge[i];
                if (!vis[e.to]&&e.cap>e.flow) {
                    vis[e.to]=1;
                    deep[e.to]=deep[u]+1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int dfs(int u,int in)
    {
        if (in==0||u==t) {
            return in;
        }
        int f=0,out=0;
        for (int &i=cur[u];i!=-1;i=next[i]) {
            Edge &e=edge[i];
            if (deep[e.to]==deep[u]+1&&(f=dfs(e.to,min(in,e.cap-e.flow)))>0) {
                edge[i].flow+=f;
                edge[i^1].flow-=f;
                in-=f;
                out+=f;
                if (in==0) {
                    break;
                }
            }
        }
        return out;
    }

    int maxflow()
    {
        int ans=0;
        while (bfs()) {
            for (int i=0;i<6*maxn;i++) {
                cur[i]=head[i];
            }
            ans+=dfs(s,INF);
        }
        return ans;
    }

}DC;

int main()
{
    DC.init();
    cin>>n;
    string tmp;
    for (int i=0;i<n;i++) {
        cin>>tmp;
        rec[tmp]=rec_cnt;
        DC.addEdge(rec_cnt,601,1);
        rec_cnt++;
    }
    cin>>m;
    for (int i=0;i<m;i++) {
        cin>>tmp;
        dev[tmp]=dev_cnt;
        DC.addEdge(0,dev_cnt,1);
        cin>>tmp;
        if (rec[tmp]==0) {
            rec[tmp]=rec_cnt++;
        }
        DC.addEdge(dev_cnt,rec[tmp],1);
        dev_cnt++;
    }
    cin>>k;
    string in,out;
    for (int i=0;i<k;i++) {
        cin>>in;
        cin>>out;
        if (rec[in]==0) {
            rec[in]=rec_cnt++;
        }
        if (rec[out]==0) {
            rec[out]=rec_cnt++;
        }
        DC.addEdge(rec[in],rec[out],INF);
    }
    printf("%d\n",dev_cnt-1-DC.maxflow());
    return 0;
}

代码解释

1. 输入处理：
   • 读取插座数量 $n$ 和插座类型。
   • 读取设备数量 $m$ 和设备名称及其插头类型。
   • 读取适配器数量 $k$ 和适配器的转换关系。
2. 网络流模型构建：
   • 源点连接到所有设备节点，容量为 1。
   • 设备节点连接到对应的插座类型节点，容量为 1。
   • 插座类型节点通过适配器连接到其他插座类型节点，容量为无穷大。
   • 插座类型节点连接到汇点，容量为 1。
3. 最大流计算：
   • 使用 Dinic 算法计算从源点到汇点的最大流。
4. 结果输出：
   • 无法插入的设备数量为 $m - \text{maxflow}$。