(图文无关)
正题开始前的吐槽
- 这强行UNIX我给满分......
- 输入真恶心,建图真麻烦......
正题开始
这是一道最大流的问题,题目大意就是说有若干个设备,每个设备都对应一种插头类型;有若干种插座类型,同时还有若干种插头类型转换器,转换器的数量是无限的,问不能成功配对(即插头插到对应类型的插座上)的设备最少是多少。
思路的话其实不难想:可以建立一个超级源点和一个超级汇点,从源点到每种设备之间各连一条容量为1的边;从插座到汇点之间各连一条容量为1的边。对于转换器,很容易想到将所有转换关系转换为一张有向图。我们可以使用floyd求该图上任意两点间的最长路,以此来计算两点之间是否连通,即两种插头之间是否可以转化。如果插头A可以转换为插头B,在网络上将插头类型为A的设备与插座类型为B的插座间连一条边,容量为1(其实只要>=1即可)。最后Dinic求一下最大流,最大流对应的就是最多可以匹配的设备。
<p>floyd求最长路时最好把点数调大一点,500比较合适!否则会WA!</p>
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m,k;
int con[1005][1005];
struct node{
int id;
string type;
node(int id,string type):id(id),type(type){
}
};
struct edge{
int to;
int cap;
ull rev;
edge(int to,int cap,ull rev):to(to),cap(cap),rev(rev){
}
};
vector<node> rec;
vector<node> plug;
map<string,int> mp;
vector<edge> gra[1005];
int cur[1005];
void floyd(int nn)
{
for(int k=1;k<=nn;k++){
for(int i=1;i<=nn;i++){
for(int j=1;j<=nn;j++){
if(con[i][k]&&con[k][j])
con[i][j]=max(con[i][j],con[i][k]+con[k][j]);
}
}
}
}
//mp用于floyd时求连通性
int dep[1005];
int bfs(int s,int t)
{
queue<int> que;
memset(dep,-1,sizeof(dep));
dep[s]=0;
que.push(s);
while(!que.empty()){
int now=que.front();
que.pop();
for(int i=0;i<gra[now].size();i++){
if(gra[now][i].cap>0&&dep[gra[now][i].to]==-1){
dep[gra[now][i].to]=dep[now]+1;
que.push(gra[now][i].to);
}
}
}
return dep[t]!=-1;
}
int dfs(int st,int t,int mini)
{
if(st==t)
return mini;
for(int& i=cur[st];i<gra[st].size();i++){
edge& now=gra[st][i];
if(now.cap>0&&dep[now.to]==dep[st]+1){
int d=dfs(now.to,t,min(now.cap,mini));
if(d>0){
now.cap-=d;
gra[now.to][now.rev].cap+=d;
return d;
}
}
}
return 0;
}
int Dinic(int st,int e)
{
int ans=0;int tmp;
while(bfs(st,e)){
memset(cur,0,sizeof(cur));
while((tmp=dfs(st,e,INF))>0)
ans+=tmp;
}
return ans;
}
void add(int from,int to,int wei)
{
gra[from].push_back(edge(to,wei,gra[to].size()));
gra[to].push_back(edge(from,0,gra[from].size()-1));
}
int main()
{
memset(con,0,sizeof(con));
cin>>n;int idx=1;int idx1=1;
for(int i=1;i<=n;i++){
string str;
cin>>str;
rec.push_back(node(idx1,str));
idx1++;
mp[str]=idx++;
}
cin>>m;
for(int i=1;i<=m;i++){
string str1,str2;
cin>>str1>>str2;
plug.push_back(node(idx1,str2));
idx1++;
if(!mp.count(str2))
mp[str2]=idx++;
else
idx++;
}
cin>>k;
for(int i=1;i<=k;i++){
string a,b;
cin>>a>>b;
if(!mp.count(a))
mp[a]=idx++;
if(!mp.count(b))
mp[b]=idx++;
con[mp[a]][mp[b]]=1;
}
floyd(idx);
for(int i=0;i<plug.size();i++){
for(int j=0;j<rec.size();j++){
node& n1=plug[i];
node& n2=rec[j];
if(con[mp[n1.type]][mp[n2.type]]||n1.type==n2.type){ //转换器之间连边
add(n1.id,n2.id,2);
}
}
}
for(int i=0;i<plug.size();i++)
add(0,plug[i].id,1);
for(int i=0;i<rec.size();i++){
add(rec[i].id,500,1);
}
int maxi_flow=Dinic(0,500);
cout<<m-maxi_flow<<endl;
}
附录
因为这题用到了最短(长)路,所以顺便复习以下最短路常用的三种算法:
dijkstra
可用于求单个点到图上其他点的最短路;基于贪心思想;不可用于有负权边的图
floyd
可用于求图上任意两个点之间的最短路;基于动态规划思想;可以处理有负权边的图,但不能处理有负环的图
SPFA
队列优化版的Bellmon-Ford,可用于求单个点到图上其他点的最短路;可以处理有负权边的图;还可以用于判断一个图是否有负环,即判断某个点的入队次数是否大于n(图上点的总数),如果是就说明存在负环。要注意的是,SPFA可能会被恶意数据卡掉,谨慎使用