首页 技术 正文
技术 2022年11月24日
0 收藏 306 点赞 4,716 浏览 2110 个字

题意:

有n个插座,m个设备以及k种转化器(每种转化器视为有无限个)。

转换器A->B可以将A类型的插头转化成B类型的插头,所以可以插在B类型的插座上。

求最少剩多少不匹配的设备。

分析:

抛开转换器不讲,插头插在插座上就是一个最大二分图匹配。

可以用最大流的算法,增加一个连接每个插头的源点s和连接每个插座的汇点t,每条弧容量都为1.

然后求最大流量,就是二分图的最大基数匹配。

既然有了转换器,一种插头可以用转换器转换成多种类型的插头,所以可以Floyd一次,求出每种插头可以转换成的所有的插头类型。

然后构二分图,求最大匹配即可。

 #include <bits/stdc++.h> using namespace std; const int maxn =  + ; vector<string> names;
int ID(const string& s)
{
for(int i = ; i < names.size(); ++i)
if(names[i] == s) return i;
names.push_back(s);
return names.size() - ;
} int n, m, k;
bool d[maxn][maxn];
int target[maxn], device[maxn]; const int INF = ; struct Edge
{
int from, to, cap, flow;
Edge(int u=, int v=, int c=, int f=):from(u), to(v), cap(c), flow(f) {}
}; struct EdmondsKarp
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int a[maxn];
int p[maxn]; void Init(int n)
{
for(int i = ; i < n; ++i) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int cap)
{
edges.push_back(Edge(from, to, cap, ));
edges.push_back(Edge(to, from, , ));
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
} int MaxFlow(int s, int t)
{
int flow = ;
for(;;)
{
memset(a, , sizeof(a));
queue<int> Q;
Q.push(s);
a[s] = INF;
while(!Q.empty())
{
int x = Q.front(); Q.pop();
for(int i = ; i < G[x].size(); ++i)
{
Edge& e = edges[G[x][i]];
if(!a[e.to] && e.cap > e.flow)
{
p[e.to] = G[x][i];
a[e.to] = min(a[x], e.cap - e.flow);
Q.push(e.to);
}
}
if(a[t]) break;
}
if(!a[t]) break;
for(int u = t; u != s; u = edges[p[u]].from)
{
edges[p[u]].flow += a[u];
edges[p[u]^].flow -= a[u];
}
flow += a[t];
}
return flow;
}
}; EdmondsKarp g; int main()
{
//freopen("in.txt", "r", stdin);
int T;
scanf("%d", &T);
while(T--)
{
names.clear();
memset(d, , sizeof(d));
string s1, s2;
scanf("%d", &n);
for(int i = ; i < n; ++i) { cin >> s1; target[i] = ID(s1); }
scanf("%d", &m);
for(int i = ; i < m; ++i) { cin >> s1 >> s2; device[i] = ID(s2); }
scanf("%d", &k);
for(int i = ; i < k; ++i) { cin >> s1 >> s2; d[ID(s1)][ID(s2)] = true; }
//Floyd
int V = names.size();
for(int k = ; k < V; ++k)
for(int i = ; i < V; ++i)
for(int j = ; j < V; ++j)
d[i][j] |= d[i][k] && d[k][j]; //Build Graph
g.Init(V+);
for(int i = ; i < m; ++i) g.AddEdge(V, device[i], );//源点到每个设备
for(int i = ; i < n; ++i) g.AddEdge(target[i], V+, );//每个插座到汇点
for(int i = ; i < m; ++i)
for(int j = ; j < n; ++j)
if(d[device[i]][target[j]]) g.AddEdge(device[i], target[j], INF);
int ans = g.MaxFlow(V, V+);
printf("%d\n", m-ans);
if(T) puts("");
} return ;
}

代码君

紫书后面又介绍了一种更简单的做法,就是直接把k种转换器对应的k条弧加到图中去,然后求最大流。

代码就不贴了,=_=||

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141977.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,508
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,314
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站