网络流，设备、插头和转接器建图(简单map的应用)

题意：

给你n个插座，m个设备，每台设备都有对应的插座，有k个转接器。
要求：求满足不能插上插座的用电器最少个数
solution:

HINT：每种适配器都有无限个，所以建图的时候要改为INF。
答案为m-idnic()
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<queue>
  6 #include<map>
  7 #include<cstring>
  8 #define mp make_pair
  9 #define pb push_back
 10 #define first fi
 11 #define second se
 12 #define pw(x) (1ll << (x))
 13 #define sz(x) ((int)(x).size())
 14 #define all(x) (x).begin(),(x).end()
 15 #define rep(i,l,r) for(int i=(l);i<(r);i++)
 16 #define per(i,r,l) for(int i=(r);i>=(l);i--)
 17 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)
 18 #define eps 1e-9
 19 #define PIE acos(-1)
 20 #define cl(a,b) memset(a,b,sizeof(a))
 21 #define fastio ios::sync_with_stdio(false);cin.tie(0);
 22 #define lson l , mid , ls
 23 #define rson mid + 1 , r , rs
 24 #define ls (rt<<1)
 25 #define rs (ls|1)
 26 #define INF 0x3f3f3f3f
 27 #define LINF 0x3f3f3f3f3f3f3f3f
 28 #define freopen freopen("in.txt","r",stdin);
 29 #define cfin ifstream cin("in.txt");
 30 #define lowbit(x) (x&(-x))
 31 #define sqr(a) a*a
 32 #define ll long long
 33 #define ull unsigned long long
 34 #define vi vector<int>
 35 #define pii pair<int, int>
 36 #define dd(x) cout << #x << " = " << (x) << ", "
 37 #define de(x) cout << #x << " = " << (x) << "
"
 38 #define endl "
"
 39 using namespace std;
 40 int n,m,k;
 41 const int maxn=505;
 42 map<string,int>ids; 
 43 
 44 struct Edge{
 45     int u,v,cap;
 46 };
 47 int S,T;
 48 vi G[maxn];
 49 int dep[maxn]; 
 50 vector<Edge> edge;
 51 inline int id(string s)
 52 {
 53     int m=sz(ids);
 54     if(ids.count(s))return ids[s];
 55     return ids[s]=m; 
 56 }
 57 
 58 void addedge(int u,int v,int cap)
 59 {
 60     edge.pb((Edge){u,v,cap});
 61     edge.pb((Edge){v,u,0});
 62     int t=sz(edge);
 63     G[u].pb(t-2);
 64     G[v].pb(t-1);
 65 }
 66 
 67 bool bfs()
 68 {
 69     cl(dep,-1);
 70     int Q[maxn]; 
 71     int h=0,t=1;dep[S]=0;Q[t]=S;
 72     while(h<t){
 73 //        de(T);
 74         int x=Q[++h];
 75         if(x==T)return 1;
 76         rep(i,0,sz(G[x])){
 77             Edge& e=edge[G[x][i]];
 78 //            de(e.v);puts("here");
 79             if(dep[e.v]==-1&&e.cap){
 80                 dep[e.v]=dep[x]+1;
 81                 Q[++t]=e.v;
 82             }
 83         }
 84     }
 85     return 0;
 86 }
 87 int dfs(int x,int f)
 88 {
 89     if(x==T)return f;
 90     int used=0,t;
 91     rep(i,0,sz(G[x])){
 92         Edge& e=edge[G[x][i]];
 93 //        dd(e.u),de(e.v);
 94         if(e.cap&&dep[e.v]==dep[x]+1){
 95             t=dfs(e.v,min(e.cap,f));
 96             e.cap-=t;edge[G[x][i]^1].cap+=t;
 97             used+=t;f-=t;
 98             if(!f)return used;
 99         }
100     }
101     if(!used)dep[x]=-1;
102     return used;
103 }
104 int dinic()
105 {
106     int ans=0;
107     while(bfs())ans+=dfs(S,INF);
108     return ans;
109 }
110 void mapping()
111 {
112     S=0;
113     string in[maxn],out[maxn];id("S");
114     cin>>n;
115     FOR(i,1,n)cin>>in[i];
116     cin>>m;
117     FOR(i,n+1,n+m)cin>>in[i]>>out[i],addedge(0,id(in[i]),1),addedge(id(in[i]),id(out[i]),1);
118     cin>>k;
119     FOR(i,n+m+1,n+m+k)cin>>in[i]>>out[i],addedge(id(in[i]),id(out[i]),INF);
120 //    FOR(i,1,n)dd(in[i]),de(id(in[i]));
121     T=n+m+k+1;
122     FOR(i,1,n)addedge(id(in[i]),T,1);
123 }
124 int main()
125 {
126     mapping();
127     cout<<m-dinic()<<endl;
128     return 0;
129 }
View Code