POJ 1087 ZOJ 1157 插头和插座 网络流 繁琐 不喜欢

这个题的做法我已经知道，就是先构造出图，用网络流算法走个最大流，由于只有插头插座两种，也可以用二分图（二部图）匹配，但是要我写代码，感觉很烦躁，拖了很久，终于用网络流A了它。

记录第一次用map，呵呵。因为老是要做查找操作，所以试试map，希望能省点时间。

构图方式如下：

加入超源点s和超收点t

s点到所有插座的容量为1（因为该插座只有一个）

设备要用的插头到t点的容量为该类型插头的个数（例如有3个设备是B插头，插头B到t的容量为3）

插头能直接插在插座上（名字相同），那么插座到插头的容量为无穷。

插头能通过交换器连接到插座上，该插座到插头的容量也为无穷，用最大流算法求出能输送多少到超收点。

再用设备数-该值即为所求。

先贴POJ上能过的较繁琐，但是可能更直观的代码：

View Code 
  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 using namespace std;
  8 #define MAXN 300
  9 #define INF 0x7fffffff
 10 map<string,int> mp;//原插座和设备
 11 map<string,int> c;//转换器
 12 bool edge[MAXN][MAXN];//转换器的邻接矩阵
 13 int ss,tt;//源点和汇点
 14 int n,m;
 15 int cur,ser;//设备和插座的点数，转换器中出现了多少种插头和插座
 16 int resi[MAXN][MAXN];  //容量网络
 17 bool sign[MAXN][MAXN];  //层次网络
 18 int reach[MAXN][MAXN];//每个点的可到达点
 19 int qua[MAXN];//每个点的可到达多少个点
 20 int num[MAXN];//设备的数量要求
 21 char a[MAXN][30];//存转换器中的插头插座名字
 22 char aa[MAXN][30];
 23 void init1()//读入会议室提供的插座和设备所需插座
 24 {
 25     int i;
 26     memset(num,0,sizeof(num));
 27     scanf("%d",&n);
 28     for(i=0; i<n; ++i)
 29     {
 30         cin>>aa[i];
 31         mp[aa[i]] = i;
 32     }
 33     scanf("%d",&m);
 34     cur = n-1;
 35     for(i=0; i<m; ++i)
 36     {
 37         string d,dname;
 38         cin>>dname>>d;
 39         d = d+'d';
 40         map<string,int>::iterator it;
 41         it = mp.find(d);
 42         if(it != mp.end())
 43             ++num[(*it).second];
 44         else
 45         {
 46             mp[d] = ++cur;
 47             strcpy(aa[cur],d.c_str());
 48             num[cur] = 1;
 49         }
 50     }
 51     for(int i=0; i<n; ++i)
 52     {
 53         map<string,int>::iterator it;
 54         string sq = aa[i];
 55         sq = sq + 'd';
 56         it = mp.find(sq);
 57         if(it != mp.end())
 58             resi[i][(*it).second] = INF;
 59     }
 60     ss = cur+1;
 61     tt = cur+2;
 62 }
 63 void init2()//读入转换器的情况,构造出转换的邻接矩阵
 64 {
 65     int k;
 66     scanf("%d",&k);
 67     memset(edge,0,sizeof(edge));
 68     ser=-1;
 69     while(k--)
 70     {
 71         string s2,s1;
 72         cin>>s2>>s1;
 73         map<string,int>::iterator it1,it2;
 74         int id1,id2;
 75         it1 = c.find(s1);
 76         if(it1 == c.end())
 77         {
 78             c[s1] = ++ser;
 79             strcpy(a[ser],s1.c_str());
 80             id1 = ser;
 81         }
 82         else
 83             id1 = (*it1).second;
 84         it2 = c.find(s2);
 85         if(it2 == c.end())
 86         {
 87             c[s2] = ++ser;
 88             strcpy(a[ser],s2.c_str());
 89             id2 = ser;
 90         }
 91         else
 92             id2 = (*it2).second;
 93         edge[id1][id2] = 1;
 94     }
 95 }
 96 void init3()//把能通过某插座让某设备工作的resi[u][v] =INF
 97 {
 98     queue<int>Q;
 99     memset(qua,0,sizeof(qua));
100     for(int i=0; i<=ser; ++i)
101     {
102         Q.push(i);
103         while(!Q.empty())
104         {
105             int u = Q.back();
106             Q.pop();
107             for(int j=0; j<=ser; ++j)
108             {
109                 if(edge[u][j] == 1)
110                 {
111                     Q.push(j);
112                     reach[i][qua[i]++] = j;
113                 }
114             }
115         }
116     }
117     for(int i=0; i<=ser; ++i)
118     {
119         string s = a[i];
120         map<string,int>::iterator it1,it2;
121         it1 = mp.find(s);
122         if(it1 != mp.end())
123         {
124             int u = (*it1).second;
125             for(int j=0; j<qua[i]; ++j)
126             {
127                 string str = a[reach[i][j]];
128                 str = str+'d';
129                 it2 = mp.find(str);
130                 if(it2 != mp.end())
131                 {
132                     int v = (*it2).second;
133                     resi[u][v] = INF;
134                 }
135             }
136         }
137     }
138     for(int i=0; i<n; ++i)
139         resi[ss][i] = 1;
140     for(int i=n; i<=cur; ++i)
141         resi[i][tt] = num[i];
142 }
143 void pushRelabel()//预流推进算法
144 {
145     queue<int>act;
146     int ef[MAXN],h[MAXN];
147     int i;
148     int sum = 0;
149     int u,p;
150     memset(ef,0,sizeof(ef));
151     memset(h,0,sizeof(h));
152     h[ss] = cur+3;
153     ef[ss] = INF;
154     ef[tt] = -INF;
155     act.push(ss);
156     while(!act.empty())
157     {
158         u =act.front();
159         act.pop();
160         for(i=0; i<=cur+2; ++i)
161         {
162             p = min(resi[u][i],ef[u]);
163             if(p>0 &&(u == ss || h[u] == h[i]+1))
164             {
165                 resi[u][i] -= p;
166                 resi[i][u] += p;
167                 ef[u] -= p;
168                 ef[i] += p;
169                 if(i == tt)
170                     sum += p;
171                 if(i != ss && i != tt)
172                     act.push(i);
173             }
174         }
175         if(u != ss && u != tt && ef[u] >0)
176         {
177             ++h[u];
178             act.push(u);
179         }
180     }
181     printf("%d\n",m-sum);//直接在这里输出结果
182 }
183 int main()
184 {
185     freopen("in.cpp","r",stdin);
186     init1();
187     init2();
188     init3();
189     pushRelabel();
190     return 0;
191 }

该代码在ZOJ上交超时，没办法，只得想办法优化，自我感觉也没有优化多少，ZOJ给10s我都超时，“优化”完后，100ms内 过了，不理解

ZOJ的代码：

View Code 
  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 using namespace std;
  8 #define MAXN  400
  9 #define INF 0x7fffffff
 10 #define min(a,b) a<b?a:b
 11 map<string,int>mp;//原插座转换器
 12 map<string,int>dev;
 13 bool edge[MAXN][MAXN];//原插座+转换器的邻接矩阵
 14 int ss,tt;//源点和汇点
 15 int n,m;
 16 int cur,ser;//原插座+设备的数目
 17 int resi[MAXN][MAXN];  //容量网络
 18 char a[MAXN][30];//存转换器中的插头插座名字
 19 void init1()//读入会议室提供的插座和设备所需插座
 20 {
 21     int i;
 22     map<string,int>::iterator it;
 23     memset(resi,0,sizeof(resi));
 24     scanf("%d",&n);
 25     for(i=0; i<n; ++i)
 26     {
 27         cin>>a[i];
 28         mp[a[i]] = i;
 29     }
 30     ss = n;
 31     tt = n+1;
 32     scanf("%d",&m);
 33     cur = n+1;
 34     for(i=0; i<m; ++i)
 35     {
 36         string d,dname;
 37         cin>>dname>>d;
 38         it = dev.find(d);
 39         if(it != dev.end())
 40             ++resi[(*it).second][tt];
 41         else
 42         {
 43             dev[d] = ++cur;
 44             resi[cur][tt] = 1;
 45         }
 46     }
 47     for(int i=0; i<n; ++i)
 48     {
 49         resi[ss][i] = 1;
 50         string s = a[i];
 51         it = dev.find(s);
 52         if(it != dev.end())
 53             resi[i][(*it).second] = INF;
 54     }
 55 }
 56 void init2()//读入转换器的情况,构造出转换的邻接矩阵
 57 {
 58     int k;
 59     map<string,int>::iterator it1,it2;
 60     scanf("%d",&k);
 61     memset(edge,0,sizeof(edge));
 62     ser = n-1;
 63     while(k--)
 64     {
 65         string s1,s2;
 66         cin>>s2>>s1;
 67         int id1,id2;
 68         it1 = mp.find(s1);
 69         if(it1 == mp.end())
 70         {
 71             mp[s1] = ++ser;
 72             strcpy(a[ser],s1.c_str());
 73             id1 = ser;
 74         }
 75         else
 76             id1 = (*it1).second;
 77         it2 = mp.find(s2);
 78         if(it2 == mp.end())
 79         {
 80             mp[s2] = ++ser;
 81             strcpy(a[ser],s2.c_str());
 82             id2 = ser;
 83         }
 84         else
 85             id2 = (*it2).second;
 86         edge[id1][id2] = 1;
 87     }
 88 }
 89 void init3()//如果v设备插的插座可以由u转来，那么resi[u][v] = INF
 90 {
 91     queue<int>Q;
 92     map<string,int>::iterator it;
 93     for(int i=0; i<n; ++i)
 94     {
 95         Q.push(i);
 96         while(!Q.empty())
 97         {
 98             int u = Q.front();
 99             Q.pop();
100             for(int j=0; j<=ser; ++j)
101             {
102                 if(edge[u][j] == 1)
103                 {
104                     Q.push(j);
105                     string s = a[j];
106                     it = dev.find(s);
107                     if(it != dev.end())
108                         resi[i][(*it).second] = INF;
109                 }
110             }
111         }
112     }
113 }
114 void pushRelabel()
115 {
116     queue<int>act;
117     int ef[MAXN],h[MAXN];
118     int i;
119     int sum = 0;
120     int u,p;
121     memset(ef,0,sizeof(ef));
122     memset(h,0,sizeof(h));
123     h[ss] = cur+1;
124     ef[ss] = INF;
125     ef[tt] = -INF;
126     act.push(ss);
127     while(!act.empty())
128     {
129         u =act.front();
130         act.pop();
131         for(i=0; i<=cur; ++i)
132         {
133             p = min(resi[u][i],ef[u]);
134             if(p>0 &&(u == ss || h[u] == h[i]+1))
135             {
136                 resi[u][i] -= p;
137                 resi[i][u] += p;
138                 ef[u] -= p;
139                 ef[i] += p;
140                 if(i == tt)
141                     sum += p;
142                 if(i != ss && i != tt)
143                     act.push(i);
144             }
145         }
146         if(u != ss && u != tt && ef[u] >0)
147         {
148             ++h[u];
149             act.push(u);
150         }
151     }
152     printf("%d\n",m-sum);
153 }
154 int main()
155 {
156 //    freopen("in.cpp","r",stdin);
157     int T;
158     scanf("%d",&T);
159     while(T--)
160     {
161         mp.clear();
162         dev.clear();
163         init1();
164         init2();
165         init3();
166         pushRelabel();
167         if(T != 0)
168             puts("");
169     }
170     return 0;
171 }

 代码的长度也有所减少啊

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/allh123/p/3047921.html