首页 > 代码库 > maxflow1087E-K
maxflow1087E-K
poj 1087 （最大流或二分匹配）
题意其实容易读懂，就是：
1、在一个会议室里有n种插座，每种插座一个；
2、每个插座只能插一种以及一个电器（或者适配器）；
3、有m个电器，每个电器有一个插头需要插在相应一种插座上；
4、不是所有电器都能在会议室找到相应插座；
5、有k种适配器，每种适配器可以有无限多数量；
6、每种适配器(a, b)可以把b类插座变为a类插座；
7、问最后有多少个电器无法使用。
本题可以用最大流或者二分图做。
下面讲解最大流：
按照电流流向构图
1、各个电器各自为一个节点，和源点（不存在，自己构造）相连，且源点到电器的容量为1。
2、将室内已有的插座各自为一个节点，和汇点（不存在，自己构造）相连，且到汇点的容量为1。
3、将电器到其应该插的插座类型的点做边，且容量为1。
4、将适配器(a, b)从a点到b点做边，且边的容量为INF。
需要注意，在输入电器以及输入适配器的过程中，如果遇到室内没有的插座类型，则需要在图中添加新的节点。
#include <iostream>
#include <queue>
#include <map>
#include<string>
using namespace std;
const int INF = 0x7fffffff;
const int MAX = 600;
int r[MAX][MAX] , pre[MAX] , d[MAX];
map < string ,int > hash;
queue < int > Q;
int karp(int s,int t,int num)
{
int Maxflow=0;
while (1)
{
memset(pre,-1,sizeof(pre));
memset(d,0,sizeof(d));//找到一条增广路径后，重新把最小残余值(指的是顶点的，不是边)初始为0
while (!Q.empty())Q.pop();
Q.push(s);
d[s]=INF;//d[i]表示从源点到i点经过的路径最小残留量，目的在于获取增广路径的最小残留量，即d[t]的残留量，
while (!Q.empty())
{
int q=Q.front(); Q.pop();
for (int i=1;i<=num;i++)
{
if (d[i]==0&&r[q][i]>0)//d[i]=0表示没有被访问过，r>0表示存在边。r初始为0
{
pre[i]=q;
d[i]=d[q] > r[q][i] ? r[q][i] : d[q] ; //取两者更小的
Q.push(i);
}
}
}
if (d[t]==0)break;//搜索不到t说明不存在增广路径，跳出while执行return Maxflow;
for (int i=t;i!=s;i=pre[i])
{
r[pre[i]][i]-=d[t];//d[t]是增广路径上最小的残留量
r[i][pre[i]]+=d[t]; //反方向的也要考虑
}
Maxflow+=d[t];
}
return Maxflow;
}
int main()
{
int l,m,n;/* l:室内插座数量； m:电器的数量;n:适配器种类数;*/
char tmp1[30],tmp2[30];
int s=1,t=2;//一号节点为源点，二号为汇点
scanf("%d",&l);
int num=3; //从3开始
memset(r,0,sizeof(r));
for (int i=1;i<=l;i++)
{
scanf("%s",tmp1); //插座盒、电器均有名称。
hash[tmp1]=num;//第NUM个节点对应名字为temp1的插座
//用map容器将string类型的电器映射到数字，即将其编号，同时以方便后面查重
r[num++][t]=1;//权值为1，表示插座最多只能有一个电器经过，且最终流入汇点
}
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
scanf("%s%s", tmp1 , tmp2 ); //temp1电器，temp2插座
hash[tmp1]=num;
r[s][num++]=1;//电器与源点s相连，最多只能有一个电器被使用
if (hash.count(tmp2)==0)//如果出现之前没有出现的插座，表示该电器应该用该插座，但目前没有，不过后面用适配器可以转换
{
hash[tmp2]=num++;
}
r[hash[tmp1]][hash[tmp2]]=1;//电器与插座相连
}
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%s%s",tmp1,tmp2);
if (hash.count(tmp1)==0)//也可能出现之前没出现过的
{
hash[tmp1]=num++;
}
if (hash.count(tmp2)==0)
{
hash[tmp2]=num++;
}
r[hash[tmp1]][hash[tmp2]]=INF;//适配器无数个，所以残留量无限大。
}
printf("%d\n",m-karp(s,t,num));
//system("pause");
return 0;
}
maxflow1087E-K