POJ1087A Plug for UNIX(会议室的插座)――最大流 - c++编程基础

TOP

POJ1087A Plug for UNIX(会议室的插座)――最大流

2015-07-20 17:16:24 来源: 作者: 【大中小】浏览:2次

题目描述：
现在由你负责布置Internet 联合组织首席执行官就职新闻发布会的会议室。
由于会议室修建时被设计成容纳全世界各地的新闻记者，因此会议室提供了多种电源插座用
以满足（会议室修建时期）各国不同插头的类型和电压。不幸的是，会议室是很多年前修建的，
那时新闻记者很少使用电子设备，所以会议室对每种插座只提供了一个。新闻发布会时，新闻记
者需要使用许多电子设备，如手提电脑，麦克风，录音机，传呼机等等。尽管这些设备很多可以
使用电池，但是由于发布会时间很长并且是单调乏味的，记者们希望能够使用尽可能多的设备（这
些设备需要使用插座），以打发时间。
在发布会之前，你收集了记者们使用的设备的信息，开始布置会议室。你注意到有些设备的
插头没有合适的插座可用。你怀疑这些设备来自那些在修建会议室时不存在的国家。对有些插座
来说，有多个设备的插头可以使用。而对另一些插座来说，没有哪些设备的插头可以用得上。
为了试图解决这个问题，你光顾了附近的商店，商店出售转换器，这些转换器可以将一种插
头转换成另一种插头。而且转换器可以串联。商店没有足够多的转换器类型，满足所有的插头和
插座的组合，但对于已有某种转换器，总是可以提供无限多个。

输入描述：
输入文件包含多个测试数据。输入文件的第一行为一个整数N，然后隔一个空行之后是N 个
输入块，每个输入块对应一个测试数据。输入块之间用空行隔开。每个输入块格式为：
每个输入块的第一行为一个正整数n，1≤n≤100，表示会议室提供的插座个数；接下来n
行列出了会议室提供的n 个插座，每个插座用一个数字字母式字符串描述（至多有24 个字符）；
接下来一行为一个正整数m，1≤m≤100，表示待插入的设备个数；接下来m 行中，每行首
先是设备的名称，然后是它使用的插头的名称；插头的名称跟它所使用的插座的名称是一样的；
设备名称是一个至多包含24 个字母数字式字符的字符串；任何两个设备的名称都不同；设备名称
和插头之间用空格隔开；
接下来一行为一个正整数k，1≤k≤100，表明可以使用的转换器种数；接下来的k 行，每行
描述了一种转换器：首先是转换器提供的插座类型，中间是一个空格，然后是插头的类型。

输出描述：
对输入文件中的每个测试数据，输出一个非负整数，表明至少有多少个设备无法插入。

顶多有200个插座，100个设备。源点到各个设备建一条cap为1的边，各个插座到汇点建一条cap为1的边，各个设备到匹配的插座建一条cap为1的边，插座之间的转换建一条cap为INF的边，求最大流

ISAP Memory: 336K Time: 32MS

#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          const int maxn=400; const int INF=0x3f3f3f3f; using namespace std; int n,s,t; struct Edge{ int from,to,cap,flow; Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} }; vector
         
           edges; vector
          
            G[maxn]; int gap[maxn],d[maxn],cur[maxn],p[maxn]; inline void addedge(int u,int v,int c){ edges.push_back(Edge(u,v,c,0)); edges.push_back(Edge(v,u,0,0)); int m=edges.size(); G[u].push_back(m-2); G[v].push_back(m-1); } int ISAP(){ memset(cur,0,sizeof(cur)); memset(d,0,sizeof(d)); memset(gap,0,sizeof(gap)); int x=s,flow=0,a=INF; while(d[s]
           
            e.flow&&d[e.to]+1==d[x]){ p[e.to]=G[x][i]; cur[x]=i; x=e.to; ok=1; a=min(a,e.cap-e.flow); break; } } if(!ok){ int m=n; for(int i=0;i
            
             e.flow) m=min(m,d[e.to]); } if(--gap[d[x]]==0) break; gap[d[x]=m+1]++; cur[x]=0; if(x!=s) x=edges[p[x]].from; } } return flow; } map
             
               rec; map
              
                dev; int N,M,K,cnt,cmt; void Init(){ cnt=0,cmt=200; s=302,t=303; cin>>N; for(int i=0;i
               
                >s; if(!rec.count(s)) rec[s]=++cnt; addedge(rec[s],t,1); } cin>>M; for(int i=0;i
                
                 >s1>>s2; dev[s1]=++cmt; if(!rec.count(s2)) rec[s2]=++cnt; addedge(dev[s1],rec[s2],1); addedge(s,dev[s1],1); } cin>>K; for(int i=0;i
                 
                  >s1>>s2; if(!rec.count(s1)) rec[s1]=++cnt; if(!rec.count(s2)) rec[s2]=++cnt; addedge(rec[s1],rec[s2],INF); } n=cnt+cmt-200+2; } int main() { Init(); printf(%d ,M-ISAP()); return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：LeetCode Search for a Range	下一篇：LeetCode Swap Nodes in Pairs

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: