这道题的建模不太难，基本你用过转换插头的话就明白是怎么回事了hh
1.源点与所有【已有plug】连边
2.【所有device】与汇点连边
3.该device用的插头与device连边
4.转换插头连边，这里容量是INF
网络流里流的是这种安排plug的方案可不可行，1是可行，0是不可行
做题的时候我偷了个懒，因为用了离散化，我想在最后的转接插头的时候，读进来A B，如果A插头之前没出现过，那就算B换过来也用不了；如果B之前没出现过，那根本没法换。所以我加了一行代码
if( plug_name[to]==0 || plug_name[from]==0 ) continue;
就是这行代码让我wa了好久。
这么贪心是不对的，因为可能A和0插头出现过，然后转换插头是1 0，2 1，3 2，A 3，所以就错了
#include<iostream> #include<deque> #include<vector> #include<cstring> #include<string> #include<map> #include<stdio.h> #define INF 2e9 using namespace std; int T=1000; struct edge{ int v,cap,reverse; }; vector<int> edges[1005];//邻接表 vector<edge> bian;//所有的边都存在里面 void addedge(int u,int v,int cap){//u到v一条边，再加一条反向边 edge e; e.cap=cap; e.v=v; e.reverse=bian.size()+1;//这条边的反边将建在这条边之后（这条边建完后在bian.size()的位置） bian.push_back(e); edges[u].push_back(bian.size()-1); e.cap=0; e.v=u; e.reverse=bian.size()-1; bian.push_back(e); edges[v].push_back(bian.size()-1); } int layer[1005],vis[1005]; bool count_layer(){ memset(layer,0,sizeof(layer)); deque<int> q; layer[0]=1; q.push_back(0); while( !q.empty() ){ int u = q.front(); q.pop_front(); if( u==T ) return true; for(int i=0;i<edges[u].size();i++){//所有以u为起点的边的边的索引 edge &e = bian[ edges[u][i] ]; int v=e.v; if( !layer[v] && e.cap>0 ){ layer[v] = layer[u] + 1; q.push_back( v ); } } } return false; } int dinic(){ int max_flow=0; while( count_layer() ){ memset(vis,0,sizeof(vis)); deque<int> q,path;//记录一路走过来的【点】和【边的索引】 q.push_back(0); vis[0]=1; while(!q.empty()){ int u = q.back(); if( u==T ){ int min_u,min_v,min_flow=INF; int p=0;//从0点出发 for(int i=0;i<path.size();i++){ edge &e = bian[ path[i] ]; if( e.cap<min_flow ){ min_u=p; min_flow=e.cap; } p=e.v; } p=0; max_flow+=min_flow; for(int i=0;i<path.size();i++){ edge &e = bian[ path[i] ]; e.cap-=min_flow; bian[e.reverse].cap+=min_flow; } //回溯 while( !q.empty() && q.back()!=min_u ){ vis[ q.back() ]=0; q.pop_back(); path.pop_back(); } } else{//T边 int i; for(i=0;i<edges[u].size();i++){ edge &e = bian[ edges[u][i] ]; if( layer[e.v]==layer[u]+1 && !vis[e.v] && e.cap>0 ){ vis[e.v]=1; q.push_back( e.v ); path.push_back( edges[u][i] ); break; } } if(i==edges[u].size()) { q.pop_back(); path.pop_back(); } } } } return max_flow; } int id; map<string,int> plug_name;//避免同样的插头有多个节点 int main(){ int n,m,k; cin>>n; //所有已有plug for(int i=1;i<=n;i++){ string name; cin>>name; plug_name[ name ] = ++id; addedge(0,id,1);//从源点到每个原有的plug连一个条边 } cin>>m;//所有device for(int i=1;i<=m;i++){ string name,type; cin>>name>>type; id++; addedge(id,T,1);//device到汇点建一条边 ，设汇点在1000 if( plug_name[type]==0 ){//之前没出现过这个插座 plug_name[type]= ++id; addedge(id,id-1,1);//插座到device } else addedge( plug_name[type],id,1 ); } cin>>k;//所有转接插头 for(int i=1;i<=k;i++){ string to,from; cin>>to>>from; if( plug_name[to]==0 ) plug_name[to]= ++id; if( plug_name[from]==0 ) plug_name[from]= ++id; //if( plug_name[to]==0 || plug_name[from]==0 ) continue; addedge(plug_name[from],plug_name[to],INF); } cout<<m-dinic(); return 0; }