解題報告

題意：

n個插頭m個設備k種轉換器。求有多少設備無法插入。

思路：

定義源點和匯點，源點和設備相連，容量為1.

匯點和插頭相連，容量也為1.

插頭和設備相連，容量也為1.

可轉換插頭相連，容量也為inf（由于插頭有無限個）

      #include <map>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 99999999
using namespace std;
int n,m,k,cnt,l[500],mmap[500][500],N[1000];
map<string,int >Map;
int bfs()
{
    memset(l,-1,sizeof(l));
    queue<int>Q;
    Q.push(0);
    l[0]=0;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=0;i<=cnt;i++)
        {
            if(l[i]==-1&&mmap[u][i])
            {
                l[i]=l[u]+1;
                Q.push(i);
            }
        }
    }
    if(l[cnt]>0)return 1;
    return 0;
}
int dfs(int x,int f)
{
    if(x==cnt)return f;
    int a;
    for(int i=0;i<=cnt;i++)
    {
        if(mmap[x][i]&&l[i]==l[x]+1&&(a=dfs(i,min(f,mmap[x][i]))))
        {
            mmap[x][i]-=a;
            mmap[i][x]+=a;
            return a;
        }
    }
    return 0;
}
int main()
{
    int i,j;
    string a,b;
    cin>>n;
    cnt=1;
    for(i=0;i<n;i++)
    {
        cin>>a;
        N[cnt]=1;//cha
        Map[a]=cnt++;
    }
    cin>>m;
    for(i=0;i<m;i++)
    {
        cin>>a>>b;
        N[cnt]=2;//she
        Map[a]=cnt++;
        if(Map[b]==0)
        {
            N[cnt]=3;//new1
            Map[b]=cnt++;
        }
        int u=Map[a];
        int v=Map[b];
        mmap[u][v]=1;
    }
    cin>>k;
    for(i=0;i<k;i++)
    {
        cin>>a>>b;
        if(Map[a]==0)
        {
            N[cnt]=3;
            Map[a]=cnt++;
        }
        if(Map[b]==0)
        {
            N[cnt]=3;
            Map[b]=cnt++;
        }
        int u=Map[a];
        int v=Map[b];
        mmap[u][v]=inf;
    }
    for(i=1;i<cnt;i++)
    {
        if(N[i]==1)
        {
            mmap[i][cnt]=1;
        }
        if(N[i]==2)
        {
            mmap[0][i]=1;
        }
    }
    int ans=0,t;
    while(bfs())
        while(t=dfs(0,inf))
        ans+=t;
    cout<<m-ans<<endl;
    return 0;
}

    

Description

Input

Output

Sample Input

      4 
A 
B 
C 
D 
5 
laptop B 
phone C 
pager B 
clock B 
comb X 
3 
B X 
X A 
X D 
    

Sample Output

      1