POJ 1087 A Plug for UNIX (网络最大流)

POJ 1087 A Plug for UNIX

链接:http://poj.org/problem?id=1087
题意:有n(1≤n≤100)个插座,每个插座用一个数字字母式字符串描述(至多有24 个字符)。有m(1≤m≤100)个设备,每个设备有名称,以及它使用的插头的名称;插头的名称跟它所使用的插座的名称是一样的;设备名称是一个至多包含24 个字母数字式字符的字符串;任何两个设备的名称都不同;有k(1≤k≤100)个转换器,每个转换器能将插座转换成插头。
样例:

4 A B C D 5 laptop B phone C pager B clock B comb X 3 B X X A X D

思路:建立一个汇点,每个插座和汇点连边,流量代表该种插座的个数。建立一个源点,源点和每个设备连边,流量为1。每个转换器将两个插座连边,流量为INF。然后求最大流。答案就是设备的个数减去最大流。
细节:这道题在建图的时候比较恶心。需要注意的是,在m个设备和插座以及k个转换器的数据中,可能有之前没有出现过的设备。所以必须将插座的信息存起来,可以用map来存插座对应的点。
代码:

/* ID: [email protected] PROG: LANG: C++ */ #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF (1= a; i--) #define eps 1e-6 #define debug puts("===============") #define pb push_back //#define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define POSIN(x,y) (0 mp; map :: iterator it; void init() { mem(g, 0); cnt = 1; mp.clear(); scanf("%d", &n); char str[25]; ed = 0; int tot = 1, has[111] = {0}; for (int i = 1; i v; for (int i = 0; i 0 && dist[u] == dist[e[i].v] + 1) break; if(i) { // find an admissible arc, then Advance curg[u] = i; revpath[e[i].v] = i ^ 1; u = e[i].v; } else { // no admissible arc, then relabel this vertex if(0 == (--numbs[dist[u]])) break; // GAP cut, Important! curg[u] = g[u]; int mindist = n; for(int j = g[u]; j; j = e[j].nxt) if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]); dist[u] = mindist + 1; ++numbs[dist[u]]; if(u != st) u = e[revpath[u]].v; // Backtrack } } return totalflow; } int main () { init(); printf("%d\n", m - maxflow()); return 0; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:uva 1455 - Kingdom(并查集+线段树)
下一篇:杭电1279 Stone Game(经典博弈)
相关文章

用C++ Builder实现网络连接检测程序

64位网络字节序与主机字节序转换

网络流改进SAP算法模版、HDU 1532 D

HDU 4407 Sum(12年金华网络赛-容斥

网络程序设计--UDP通信(服务器)

网络程序设计--UDP通信(客户端)

网络流 1009

网络程序设计--网络对时

AOV网络及拓扑排序

网络编程常用接口的内核实现----sys_b

图文推荐
POJ 1087 A Plug for UNIX (网络最大流)
ZOJ 3640 Help Me
POJ 1087 A Plug for UNIX (网络最大流)
CF 518C(Anya and
POJ 1087 A Plug for UNIX (网络最大流)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2013-06-07 人气:2
本文关键词:
分享到:

相关文章

  • POJ 1087 A Plug for UNIX 会议室插座问题 构图+最大流 2012-05-01

    题目链接:POJ 1087 A Plug for UNIX A Plug for UNIX Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 13809 Accepted: 4623 Description You are in charge of setting up the press room for the inaugural meeting of the United Nations Internet eXecutiv

  • POJ 1087 A Plug for UNIX(网络流之最大流) 2013-12-20

    题目地址:POJ 1087 不知道是谁把这题化为了二分最大匹配的专题里。。于是也没多想就按照二分图的模型来建的(虽然当时觉得有点不大对。。。)。后来发现二分最大匹配显然不行。。有权值。。直接来个最大流多方便。。然后一直WA。。后来仔细想了想。。这根本就不能建二分图啊。。。。这题跟二分图一点关系都没有。。。。 这题的建图思路是让源点与每一个设备的插座类型连边,让汇点与每一个插座连边。然后用floyd判断该设备能否通过转换转换成可以插的插座上。只要可以转换成的就连边,权值为INF。然后求一次最大流,

  • UVA 753 - A Plug for UNIX(网络流) 2012-11-08

    A Plug for UNIX You are in charge of setting up the press room for the inaugural meeting of the United Nations Internet eXecutive (UNIX), which has an international mandate to make the free flow of information and ideas on the Internet as cumbersome

  • HDU 1535 && POJ 1511 Invitation Cards (SPFA 模板 + 反向建图) 2012-01-31

    Invitation Cards HDU: Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) POJ: Time Limit: 8000 MS Memory Limit: 262144 K Problem Description In the age of television, not many people attend theater performances. Antique

  • HDU 2254 奥运(矩阵) 2012-04-06

    题目地址:HDU 2254 必须得吐槽一下。。这题的数据是又弱又坑。。样例不过都能AC。。还有。。居然还有重边。。WA了一晚上。。 吐槽完毕,言归正传。。 根据离散数学里面的可达矩阵的性质,我们知道一个有向图的邻接矩阵的前n次幂的和即为可达矩阵,那么要求[t1-t2]之内的路径的条数,因为题目说了t1 = 0的时候为0。那么假设邻接矩阵为A,那么要求的就是A^(t1-1)+A^(t1)+...+A^(t2-1),为什么是从t1-1开始呢,因为邻接矩阵本身代表走一步的结果。 然后再加上离散化就可以

  • uva 1455 - Kingdom(并查集+线段树) 2012-06-30

    题目链接:uva 1455 - Kingdom 题目大意:平面上又n个城市,初始时城市之间没有任何双向道路相连,要求一次执行指令。 road A B :在城市A和城市B之间连接一条双向道路 line C:询问一条y=C的水平线上穿过多少州和这些州总共有多少城市。 一个联通分量算一个州,C保证为小数部分为0.5的实数。 解题思路:线段树维护每个位置上州和城市的个数,并查集维护哪些城市属于同一个州,并且要记录这些州上下范围。每次新建一条道路,要相应根据两个州的y坐标范围对线段树进行维护。 #incl

  • 杭电1279 Stone Game(经典博弈) 2012-11-15

    Stone Game Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2539 Accepted Submission(s): 741 Problem Description This game is a two-player game and is played as follows: 1. There are n boxes; each

  • UVA11714 - Blind Sorting(推理) 2015-01-12

    题目链接 题意:给出n个数,求出得到最大数和第二大数所用的最多的比较次数 思路:可以取两个数两两做比较,就相当与建立二叉树,两个数的最大值就相当与两个的父节点,所以我们我们可以知道得到最大值时的比较次数为n-1,然后假设所有左儿子都大于右儿子,所以最大值的右儿子还有跟左子树中的值做比较得到第二大数,比较的个数为树高。 代码: #include #include #include #include #include using namespace std; int n; int main() {

  • hdu 1087 zoj 1107 FatMouse and Cheese 2013-06-24

    #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #define ll __int64 using namespace std; int mp[105][105],d[105][105],n,k; int dx[]={1,-1,0,0}; int dy[]={0,0,1,-1}; int dfs(int x,int y) { if(d[x]

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 1.884 (s). 10 q(s)