(图文无关)

A plug for UNIX

正题开始前的吐槽

  • 这强行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可能会被恶意数据卡掉,谨慎使用