紫书例题11-7 UNIX插头 （A Plug for UNIX）

题意：n个插座，m个设备，k个转换器。现在你要把这些设备插到插座上，每个设备都有对应的插头类型，使用转换器就可以“转化”插头类型。转化器的数量是无限提供的，就是插头类型可以任意转化。现在问你最少剩多少个不匹配的设备。 分析：n个插座，m个设备，两两匹配，我们不难想到这是类似于一个二分图的结构。让我们把n个出现的插座连上超级源点，但多于n的插座（会有多的）不能连上源点。再把设备连上汇点.再把插座类型连上设备。 最后，就是设备之间是可以相互转化的。我们使用最短路算法floyd求一下各个点之间的连通性。得到一个连通性数组 G[i][j]，表示i设备可以转化为j设备.然后i和j之间连一条INF的边，代表可以任意转化. 代码：

#include
using namespace std;
const int maxn = 1000;
const int INF = 1e9+5;
struct Edge{
int from,to,cap,flow;
};
struct Dicnic {
int n,m,s,t;
vector edge;vector G[maxn];
bool vis[maxn];int d[maxn],cur[maxn];
void init(int n){
for(int i=0;is=s;this->t=t;
long long flow=0;
while(bfs()){
memset(cur,0,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}

};
map mp;int cnt=0;
int id(const string & s){
if(mp.count(s)) return mp[s];
else return mp[s]=(++cnt);
}
Dicnic D;bool G[maxn][maxn];
int target[maxn],device[maxn];
int main(){
int T;cin>>T;
while(T–){
int n;cin>>n;
mp.clear();cnt=0;
for(int i=0;i>s;
target[i]=id(s);
}
int m;scanf("%d",&m);
for(int i=0;i>s1>>s2;
device[i]=id(s2);
}
int k;scanf("%d",&k);
memset(G,0,sizeof(G));
for(int i=0;i>s1>>s2;
G[id(s2)][id(s1)]=true;
}
//Floyd
int nn=mp.size();
for(int K=1;K