POJ1087 A Plug of UNIX

你作为某高管去住宿了，然后宾馆里有几种插座，分别有其对应型号，你携带了几种用电器（手机，电脑一类的），也有其对应型号；可是不一定用电器就能和插座匹配上，于是宾馆的商店里提供了一些转换器，这些转换器可以将某一型号电源转换成另一型号的。问，你的用电器最少会有多少种无法充电

源点向电器连边，容量为1，电器向对应的插座连边，容量为1，对于转换器，在插座与插座之间连边，容量为inf，所有插座向汇点连边，容量为插座的个数~

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

#include<map>

#include<iostream>

#include<string>

using namespace std;

const int maxn=;

const int inf=1e9;

queue<int> q;

int n;

int g[maxn][maxn];

int pre[maxn];

int flow[maxn];

int maxflow;

int bfs (int s,int t) {

    while (!q.empty()) q.pop();

    for (int i=;i<=n;i++) pre[i]=-;

    pre[s]=;

    q.push(s);

    flow[s]=inf;

    while (!q.empty()) {

        int x=q.front();

        q.pop();

        if (x==t) break;

        for (int i=;i<=n;i++)

        if (g[x][i]>&&pre[i]==-) {

            pre[i]=x;

            flow[i]=min(flow[x],g[x][i]);

            q.push(i);

        }

    }

    if (pre[t]==-) return -;

    else return flow[t];

}

void Edmonds_Karp (int s,int t) {

    int increase=;

    while ((increase=bfs(s,t))!=-) {

        int k=t;

        while (k!=s) {

            int last=pre[k];

            g[last][k]-=increase;

            g[k][last]+=increase;

            k=last;

        }

        maxflow+=increase;

    }

}

map<string,int> pos;

int main () {

    string s1,s2;

    int N,M,cnt,st,ed;

    while (~scanf("%d",&N)) {

        pos.clear();

        memset(g,,sizeof(g));

        maxflow=;

        st=;

        ed=;

        cnt=;

        while (N--) {

            cin>>s1;

            pos[s1]=cnt;

            g[][cnt++]=;

        }

        scanf ("%d",&M);

        for (int i=;i<M;i++) {

            cin>>s1>>s2;

            if (pos[s1]==) pos[s1]=cnt++;

            if (pos[s2]==) pos[s2]=cnt++;

            g[pos[s1]][ed]=;

            g[pos[s2]][pos[s1]]=;

        }

        scanf ("%d",&N);

        while (N--) {

            cin>>s1>>s2;

            if (pos[s1]==) pos[s1]=cnt++;

            if (pos[s2]==) pos[s2]=cnt++;

            g[pos[s2]][pos[s1]]=inf;

        }

        n=cnt-;

        Edmonds_Karp (st,ed);

        printf ("%d\n",M-maxflow);

    }

    return ;

}

巴特西

POJ1087 A Plug of UNIX

最新文章

热门文章