UVA 753 A Plug for UNIX 电器插座（最大基数匹配，网络流）-白红宇

UVA 753 A Plug for UNIX 电器插座（最大基数匹配，网络流）

阅读量：5229 次

发布时间：2019-06-14

本文共 4191 字，大约阅读时间需要 13 分钟。

题意：

　　给n个插座，m个设备（肯定要插电了），k种转换头可无限次使用（注意是单向的），问有多少设备最终是不能够插上插座的？

分析：

　　看起来就是设备匹配插座，所以答案不超过m。这个题适合用网络流来解。

　　假设每种头对应着一个编号（可以用map实现转换string到int），主要在k种转换头的建边，他们之间的转换关系就是编号与编号之间的边，因为可以无限次使用，所以容量无穷。再添加源点和汇点就建完了，汇点连接每个插座，源点连接每个设备，每边容量为1。使用增广路算法就得出解了。注意要空一行。

　　很不愿意用结构体的，但是既然用起来这么方便，就用着吧，有些题是需要用结构体的。

1 //#pragma comment(linker,"/STACK:102400000,102400000")  2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
             9 #include 
             
               10 #define LL long long 11 #define pii pair
              
                12 #define INF 0x7f7f7f7f 13 using namespace std; 14 const int N=1000000+100; 15 unordered_map
               
                 has; 16 vector
                
                  dev; 17 vector
                 
                   plug; 18 vector
                  
                    chg; 19 vector
                   
                     vect[500]; 20 int path[500]; 21 int flow[500]; 22 int edge_cnt; 23 24 struct node 25 { 26 int from; 27 int to; 28 int cap; 29 int flo; 30 }edge[N]; 31 32 void add_node(int fr,int t,int ca,int fl) 33 { 34 edge[edge_cnt].from=fr; 35 edge[edge_cnt].to=t; 36 edge[edge_cnt].cap=ca; 37 edge[edge_cnt].flo=fl; 38 vect[fr].push_back(edge_cnt++); 39 } 40 41 void build_graph(int n, int m, int k, int hui) 42 { 43 //每种型号的插口是个点 44 for(int i=0; i

que; 71 que.push_back(s); 72 flow[s]=INF; 73 while(!que.empty()) 74 { 75 int x=que.front(); 76 que.pop_front(); 77 for(int i=0; i

e.flo) 81 { 82 path[e.to]=vect[x][i]; 83 flow[e.to]=min(flow[e.from],e.cap-e.flo); 84 que.push_back(e.to); 85 } 86 } 87 if(flow[e]) return flow[e]; 88 } 89 return flow[e]; 90 } 91 92 int cal(int s, int e) 93 { 94 int big_flow=0; 95 while(true) 96 { 97 memset(flow,0,sizeof(flow)); 98 memset(path,0,sizeof(path)); 99 100 int tmp=bfs(s,e);101 if(!tmp) return big_flow;102 big_flow+=tmp;//统计流103 104 int ed=e;105 while(ed!=s)106 {107 int t=path[ed];108 edge[t].flo+=tmp;109 edge[t^1].flo-=tmp;110 ed=edge[t].from;111 }112 }113 }114 115 116 int main()117 {118 freopen("input.txt", "r", stdin);119 int n, m, t, k;120 char s3[30], s4[30];121 string s1,s2;122 cin>>t;123 while(t--)124 {125 has.clear();126 dev.clear();127 plug.clear();128 chg.clear();129 130 memset(edge,0,sizeof(edge));131 edge_cnt=0;132 for(int i=0; i<500; i++) vect[i].clear();133 int num=0;134 135 scanf("%d",&n); //插座136 for(int i=0; i

AC代码

1 //#pragma comment(linker,"/STACK:102400000,102400000")  2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
             9 #include 
             
               10 #define LL long long 11 #define pii pair
              
                12 #define INF 0x7f7f7f7f 13 using namespace std; 14 const int N=1000000+100; 15 unordered_map
               
                 has; 16 vector
                
                  dev; 17 vector
                 
                   plug; 18 vector
                  
                    chg; 19 vector
                   
                     vect[500]; 20 int path[500]; 21 int flow[500]; 22 int edge_cnt; 23 24 struct node 25 { 26 int from; 27 int to; 28 int cap; 29 int flo; 30 }edge[N]; 31 32 void add_node(int fr,int t,int ca,int fl) 33 { 34 edge[edge_cnt].from=fr; 35 edge[edge_cnt].to=t; 36 edge[edge_cnt].cap=ca; 37 edge[edge_cnt].flo=fl; 38 vect[fr].push_back(edge_cnt++); 39 } 40 41 void build_graph(int n, int m, int k, int hui) 42 { 43 //每种型号的插口是个点 44 for(int i=0; i

que; 71 que.push_back(s); 72 flow[s]=INF; 73 while(!que.empty()) 74 { 75 int x=que.front(); 76 que.pop_front(); 77 for(int i=0; i

e.flo) 81 { 82 path[e.to]=vect[x][i]; 83 flow[e.to]=min(flow[e.from],e.cap-e.flo); 84 que.push_back(e.to); 85 } 86 } 87 if(flow[e]) return flow[e]; 88 } 89 return flow[e]; 90 } 91 92 int cal(int s, int e) 93 { 94 int big_flow=0; 95 while(true) 96 { 97 memset(flow,0,sizeof(flow)); 98 memset(path,0,sizeof(path)); 99 100 int tmp=spfa(s,e);101 if(!tmp) return big_flow;102 big_flow+=tmp;//统计流103 104 int ed=e;105 while(ed!=s)106 {107 int t=path[ed];108 edge[t].flo+=tmp;109 edge[t^1].flo-=tmp;110 ed=edge[t].from;111 }112 }113 }114 115 116 int main()117 {118 freopen("input.txt", "r", stdin);119 int n, m, t, k;120 char s3[30], s4[30];121 string s1,s2;122 cin>>t;123 while(t--)124 {125 has.clear();126 dev.clear();127 plug.clear();128 chg.clear();129 130 memset(edge,0,sizeof(edge));131 edge_cnt=0;132 for(int i=0; i<500; i++) vect[i].clear();133 int num=0;134 135 scanf("%d",&n); //插座136 for(int i=0; i

AC代码

转载于:https://www.cnblogs.com/xcw0754/p/4645420.html