UNIX 插头

紫书P374

【题目类型】EK网络流+Floyd传递闭包

&题解：

看了书之后有那么一点懂了，但当看了刘汝佳代码后就完全明白了，感觉他代码写的好牛逼啊，Orz

所以就完全照着码了一份。

【时间复杂度】O(\(n^3\))

&代码：

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <queue>

#include <cstdio>

using namespace std;

const int INF = 1000000000;

const int maxn= 400+9;

vector<string> names;

int ID(const string& s){

    for(int i=0;i<names.size();i++)

        if (names[i]==s) return i;

    names.push_back(s);

    return names.size()-1;

}

struct Edge{

    int from,to,cap,flow;

};

struct EK{

    int n,m;

    vector<Edge> edges;

    vector<int> G[maxn];

    int a[maxn],p[maxn];

    void Init(int n){

        this->n=n;

        for(int i=0;i<n;i++) G[i].clear();

        edges.clear();

    }

    void AddEdge(int from,int to,int cap){

        edges.push_back((Edge){from,to,cap,0});

        edges.push_back((Edge){to,from,0,0});

        m=edges.size();

        G[from].push_back(m-2);

        G[to].push_back(m-1);

    }

    int MaxFlow(int s,int t){

        int flow=0;

        for(;;){

            memset(a,0,sizeof(a));

            queue<int> Q;

            Q.push(s);

            a[s]=INF;

            while(!Q.empty()){

                int x=Q.front(); Q.pop();

                for(int i=0;i<G[x].size();i++){

                    Edge& e=edges[G[x][i]];

                    if (!a[e.to]&&e.cap>e.flow){

                        p[e.to]=G[x][i];

                        a[e.to]=min(a[x],e.cap-e.flow);

                        Q.push(e.to);

                    }

                }

                if (a[t]) break;

            }

            if (!a[t]) break;

            for(int u=t;u!=s;u=edges[p[u]].from){

                edges[p[u]].flow+=a[t];

                edges[p[u]^1].flow-=a[t];

            }

            flow+=a[t];

        }

        return flow;

    }

};

EK g;

int n,m,k;

int d[maxn][maxn],target[maxn],device[maxn];

int ka=0;

int main()

{

#ifndef ONLINE_JUDGE

    freopen("1.in", "r", stdin);

    freopen("1.out","w",stdout);

#endif

    string s1,s2;

    int o; cin>>o;

    while(o--){

        if (ka)cout<<endl; ka=1;

        names.clear();

        cin>>n;

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

            cin>>s1;

            target[i]=ID(s1);

        }

        cin>>m;

        for(int i=0;i<m;i++){

            cin>>s1>>s2;

            device[i]=ID(s2);

        }

        memset(d,0,sizeof(d));

        cin>>k;

        for(int i=0;i<k;i++){

            cin>>s1>>s2;

            d[ID(s1)][ID(s2)]=1;

        }

        int V=names.size();

        for(int k=0;k<V;k++)

            for (int i=0;i<V;i++)

                for (int j=0;j<V;j++)

                    d[i][j]|=d[i][k]&&d[k][j];

        g.Init(V+2);

        for(int i=0;i<m;i++)

            g.AddEdge(V,device[i],1);

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

            g.AddEdge(target[i],V+1,1);

        for(int i=0;i<m;i++)

            for(int j=0;j<n;j++)

                if (d[device[i]][target[j]]) g.AddEdge(device[i],target[j],INF);

        int r=g.MaxFlow(V,V+1);

        cout<<m-r<<endl;

    }

    return 0;

}

秒客网

UVA 753 UNIX 插头(EK网络流+Floyd传递闭包)

UNIX 插头