网络流 动态建图最大流

题目链接：https://vjudge.net/problem/10508/origin
题目大意：
题意：在一个会议室里有n种插座，每种插座一个,每个插座只能插一种以及一个电器（或者适配器）,有m个电器，每个电器有一个插头需要插在相应一种插座上,不是所有电器都能在会议室找到相应插座,有k种适配器，每种适配器可以有无限多数量,每种适配器(a, b)可以把b类插座变为a类插座,问最后有多少个电器无法使用，并且插座可以连插座。

坑点：其实最初的n个插座不是全部，可能由适配器转换出来新的插座。也可能有的电器需要的插座不在n中。而是在新转化来的插座，而且要合并所有相同的插座，不然根据适配器连边时，会出现有的有两个相同的插座A，A，对于适配器（B A）有的插座并没有连上适配器（其他的建图方式可以避免这个错误）。

因为插座的数量是不确定的。我们要根据输入进行建图（保证汇点足够大这里取1000）。

样例：
3
A
A
A
3
PC A
phone B
pager B
1
B A

输入插座时A， A， A,

输入电器：

输入适配器 B A。这里是B->A，还是A->B。得判断一下。这里可以把插口A转化成插口B。所有现在能够全部匹配。因为A连边到B能够全部匹配。所以A->B是正确的。因为适配器不限个数。所以边的权值应该为正无穷。

连上汇点。

然后跑最大流。用m-最大流就是答案了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int maxn=1e5+10;
const int maxm=2e5+10;

struct E
{
    int v;   //每一条边指向的点
    int next;//指向对应点的前一条边
    int w;   //每一条边的残量

}e[maxm];

int s, t;//源点和汇点
int cut;//边的数量，从0开始编号
int head[maxm];//每一个点最后一条边的编号
int d[maxn];//分层图中标记深度
int inf=(1<<31)-1;
int cur[maxn];//cur就是记录当前点u循环到了哪一条边
int n, m, k;

void init()
{
    cut=-1;
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v, int w)
{
    cut++;
    e[cut].next=head[u];
    e[cut].v=v;
    e[cut].w=w;
    head[u]=cut;
}

void add(int u, int v, int w)
{
    addEdge(u, v, w);
    addEdge(v, u, 0);
}

int bfs()
{
    queue<int> q;
    while(!q.empty())
    {
        q.pop();
    }
    memset(d, 0, sizeof(d));
    d[s]=1;//源点深度为1
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].v, w=e[i].w;
            if(w>0&&d[v]==0)//若该残量不为0，且V[i]还未分配深度，则给其分配深度并放入队列
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    if(d[t]==0)//当汇点的深度不存在时，说明不存在分层图，同时也说明不存在增广路
    {
        return 0;
    }

    return 1;
}

int dfs(int u, int dis)//u是当前节点，dist是当前流量
{
    if(u==t)
    {
        return dis;//当已经到达汇点，直接返回
    }

    for(int &i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v, w=e[i].w;
        if((d[v]==d[u]+1)&&w!=0)//注意这里要满足分层图和残量不为0两个条件
        {
            int di=dfs(v, min(dis, w));//向下增广
            if(di>0)//若增广成功
            {
                e[i].w-=di;//正向边减
                e[i^1].w+=di;//反向边加
                return di;//向上传递
            }
        }
    }

    return 0;//否则说明没有增广路，返回0
}

int Dinic()
{
    int ans=0;//记录最大流量
    while (bfs())
    {
        for(int i=s;i<=t;i++)//每一次建立完分层图后都要把cur置为每一个点的第一条边
        {
            cur[i]=head[i];
        }
        while (int d=dfs(s,inf))
        {
            ans+=d;
        }
    }
    return ans;
}

vector<string> v;
int ID(string a)
{
    for(int i=0;i<v.size();i++)
    {
        if(v[i]==a)
        {
            return i+1;
        }
    }
    v.push_back(a);

    return v.size();
}

int main()
{
    while(~scanf("%d",&n))
    {
        string a, b;
        v.clear();
        init();
        for(int i=0;i<n;i++)
        {
            cin>>a;
            add(0, ID(a), 1);
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            add(ID(b), ID(a), 1);
            add(ID(a), 1000, 1);
        }
        scanf("%d",&k);
        for(int i=0;i<k;i++)
        {
            cin>>a>>b;
            add(ID(b), ID(a), inf);
        }
        s=0, t=1000;
        cout<<m-Dinic()<<endl;
    }

    return 0;
}