首页 > 代码库 > poj1087 A Plug for UNIX（网络流最大流）
poj1087 A Plug for UNIX（网络流最大流）
http://poj.org/problem?id=1087
好久没遇见过这么坑的题了这个题真是挫的够可以的。题目大意：你作为某高管去住宿了，然后宾馆里有几种插座，分别有其对应型号，你携带了几种用电器（手机，电脑一类的），
也有其对应型号；可是不一定用电器就能和插座匹配上，于是宾馆的商店里提供了一些转换器，这些转换器可以将某一型号电源转换成另一型号的。问，你的用电器最少会有多少种无
法充电。也就是问可以用上电的用电器的最大数目，之后用电器总数减去此可用电最大数目即可得到最小不能用电数目。
一开始以为直接将插座，转换器，用电器匹配后跑个最大流模板就行，后来发现想的太简单了。
分析：
1：用电器可直接连插座；
2：用电器可以连接转换器再连接上插座；
3：转换器之间可以相互连接；
4：转换器转换作用是双向的，比如给定转换器可对A和B进行转换，则此转换器可以将A转换成B，也可以将B转换成A；
5：每种转换器的数目是无限的；
6：一个插座只能连接产生一个出处。
7：虚拟一个源点一个汇点即可，源点到插座和插头到汇点的流量为1。
按照这些建图失误了四次之后终于成功A过了。
附加详细建图步骤的备注的AC代码和一组测试数据（测试答案应当为0）
#include <stdio.h>#include <algorithm>#include <string.h>#include <queue>using namespace std;#define oo 0x3f3f3f3fint G[1000][1000], n, m, p, vis[1000];char receptacle[500][30];char plug[500][30];struct ad{ char in[30], out[30];}adapter[500];bool bfs(int Start, int End){ memset(vis, 0, sizeof(vis)); vis[Start] = 1; queue<int>Q; Q.push(Start); while(Q.size()) { int now = Q.front(); Q.pop(); if(now == End) return true; for(int i=1; i<=End; i++) { if(!vis[i] && G[now][i]>0) { vis[i] = vis[now] + 1; Q.push(i); } } } return false;}int dfs(int Start, int End, int Maxflow){ if(Start == End) return Maxflow; int nowflow = 0; for(int i=1; i<=End; i++) { if(vis[i] == vis[Start] + 1 && G[Start][i]>0) { int flow = min(G[Start][i], Maxflow - nowflow); flow = dfs(i, End, flow); G[Start][i] -= flow; G[i][Start] += flow; nowflow += flow; if(nowflow == Maxflow) break; } } return nowflow;}int dinic(int Start, int End){ int ans = 0, s; while(bfs(Start, End)) { s = dfs(Start, End, oo); if(!s)break; ans += s; } return ans;}int main(){ while(~scanf("%d", &n)) { memset(G, 0, sizeof(G)); for(int i=1; i<=n; i++) scanf("%s", receptacle[i]); scanf("%d", &m); for(int i=1; i<=m; i++) { scanf("%*s %s", plug[i]); for(int j=1; j<=n; j++) { if(strcmp(receptacle[j], plug[i]) == 0)///插头和插座可直接连 { G[j][n+p+i] = 1; } } } scanf("%d", &p); for(int i=1; i<=p; i++) scanf("%s %s", adapter[i].in, adapter[i].out); for(int i=1; i<=p; i++)///1~n是插座，n+1~n+p是转换器，n+p+1~n+p+m是插头 { for(int j=1; j<=n; j++) { if(strcmp(receptacle[j], adapter[i].in)==0 || strcmp(receptacle[j], adapter[i].out)==0)///插座和转换器匹配 { G[j][n+i] = 1; } } for(int j=1; j<=m; j++) { if(strcmp(plug[j], adapter[i].out)==0 || strcmp(plug[j], adapter[i].in)==0)///转换器和插头匹配 { G[n+i][n+p+j] = 1; } } } for(int i=1; i<=p; i++)///转换器之间相连 { for(int j=1; j<=p; j++) { if(i!=j && strcmp(adapter[i].in, adapter[j].out)==0) G[n+i][n+j] = oo; } for(int j=1; j<=p; j++) { if(i!=j && strcmp(adapter[i].out, adapter[j].in)==0) G[n+i][n+j] = oo; } } int Start = n+p+m+1, End = Start+1; for(int i=1; i<=n; i++)///源点和插座相连 { G[Start][i] = 1; } for(int i=1; i<=m; i++)///插头和汇点相连 { G[n+p+i][End] = 1; } printf("%d\n", m - dinic(Start, End)); } return 0;}/*16ADXADADXDADDXDXD14CLOCK BCLOCK BCLOCK BLAPTOP BLAPTOP BLAPTOP BLAPTOP BLAPTOP BLAPTOP BPAGER BPAGER BCOMB XCELL CCELL C4C DX DB XB A*/
poj1087 A Plug for UNIX（网络流最大流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。