题目链接

https://vjudge.net/problem/POJ-1087

题意

n个插座，m个插头，k个转换器（B-C代表可以将B插座变成C插座，可堆叠转换器），求最少几个插头没地方插

思路

英语太差了，看题头疼

求最少几个插头没地方插，就用m-最多能插多少插头就行了。我们建立插头-插座的匹配关系，跑最大流就可以了。

具体建图部分就是，源点向所有插头连边，容量1，插头向所需插座连边，容量1，转换器的两个插座连边，容量inf（注意不是双向），所有插座向汇点连边容量1，跑最大流就行了。

插座给的都是字符串，map建立映射就可以了

代码

#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;typedef long long ll;const int inf=0x3f3f3f3f;const int maxn=10100;//开大点没坏处~~ const int maxe=200010;int head[maxn],cnt;struct Edge{int v;int w;int next;}edge[maxe];int n,m,k,s,t;ll maxflow;int deep[maxn];int now[maxe];void init(){memset(head,-1,sizeof(head));cnt=0;maxflow=0; return ;	}void add(int u,int v,int w){//	cout<<u<<" "<<v<<endl;//果然多刷题才能提高，注释的这句是我自己想出来用来调试的，哪出了岔子太好看出来了 edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;}inline bool bfs(){memset(deep,0x3f,sizeof(deep));queue<int>q;q.push(s);deep[s] = 0;now[s] = head[s];while(q.size()){int x = q.front();q.pop();for(int i=head[x];i!=-1;i=edge[i].next){int y=edge[i].v;if(edge[i].w>0&&deep[y]==inf){q.push(y);now[y]=head[y];deep[y]=deep[x]+1;if(y==t)	return 1;}}}return 0;}ll dfs(int x,int flow){if(x==t)	return flow;ll ans = 0,k,i;for(i=now[x];i!=-1&&flow;i=edge[i].next){now[x]=i;int y=edge[i].v;if(edge[i].w>0&&(deep[y]==deep[x]+1)){k=dfs(y,min(flow,edge[i].w));if(!k)	deep[y]=inf;edge[i].w-=k;edge[i^1].w+=k;ans+=k;flow-=k;}}return ans;}	void dinic(){while(bfs())maxflow+=dfs(s,inf);}map<string,int>chazuo;//建立插座和数字的映射 string need[105];//见样例，comb需要X，但第一部分输入没有X，所以先存一下，处理完再建图 int main(){	IOSinit();cin>>n;string str;s=1000,t=s+1;//查了半天错发现st写错了，下次直接写到一个根本到不了的数 for(int i=1;i<=n;i++){cin>>str;chazuo[str]=i;//1-n是插座（酒店有的） }cin>>m;for(int i=1;i<=m;i++){cin>>str;//名字无意义 cin>>need[i];}cin>>k;int ct=n+1;//可能出现新的插座类型，这个是建映射用的 for(int i=1;i<=k;i++){string s1,s2;cin>>s1>>s2;if(!chazuo[s1])chazuo[s1]=ct++;if(!chazuo[s2])chazuo[s2]=ct++;add(chazuo[s1],chazuo[s2],inf);//转换器数目无限，inf add(chazuo[s2],chazuo[s1],0);}for(int i=1;i<=m;i++){add(i+n+100,chazuo[need[i]],1);//因为总插座不一定只有n个，我们将插头从n+100+1开始编号 add(chazuo[need[i]],i+n+100,0);}for(int i=1;i<=m;i++)add(s,i+100+n,1),add(i+100+n,s,0);//源点向插头连边 for(int i=1;i<=n;i++)add(i,t,1),add(t,i,0);//插座向汇点连边 dinic();cout<<m-maxflow<<endl; return 0;}