ACM Computer Factory

POJ-3436

题目就是一个工厂n个加工机器，每个机器有一个效率w，q个材料入口，q个材料出口，每个口有三个数表示状态，1表示一定有入/出的材料，0表示没有入/出的材料，2表示可能有入的材料。如果一个机器入口全是0，代表这是起始机器，如果一个机器出口全是1，那么代表这是末尾机器。
将每个机器i拆成两点i和i+n分别代表进和出
建立超级源点，连在起始机器上，流量INF。建立超级汇点，找到末尾机器连在超级汇点上，流量INF。
一个机器拆成的两个点i和i+n连上，流量就是这个点的效率w。
然后暴力匹配，看一个点的所有出口是否可以完全对应一个点的入口，如果可以，匹配上，流量INF。
跑EK算法，得到最大流。

这里的输出路径不太理解

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

#include<sstream>

#include<vector>

#include<queue>

using namespace std;

const int maxn=110;

const int INF=0X3F3F3F3F;

int p1,n,m;

int s,t;

int q[maxn],port[maxn][maxn];

struct node{

    int from,to,flow;

};

struct Edge {

    int from, to, cap, flow;

    Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}

};

vector<Edge> edges;//这里的边是实际边数的两倍，包括反向边

vector<int> G[maxn];//邻接表，G[i][j]表示结点i的第j条边在edges数组中的序号

int a[maxn];//a[i]表示起点到i的可改进量

int p[maxn];//edges数组中的编号，最短路图上p的入弧编号

void init(int n) {

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

        G[i].clear();

    edges.clear();

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

    memset(p,0,sizeof(p));

}

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

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

    edges.push_back(Edge(to, from, 0, 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;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    while(cin>>p1>>n){

        init(2*n+1);

        s=0,t=2*n+1;

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

            cin>>q[i];

            bool flag=true;

            for(int j=0;j<p1;j++){

                cin>>port[i][j];

                if(port[i][j]==1){

                    flag=false;

                }

            }

            if(flag)

                AddEdge(s,i,INF);

            flag=true;

            for(int j=0;j<p1;j++){

                cin>>port[i+n][j];

                if(port[i+n][j]!=1)

                    flag=false;

            }

            if(flag)

                AddEdge(i+n,t,INF);

        }

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

            AddEdge(i,i+n,q[i]);

        for(int i=n+1;i<=2*n;i++){

            for(int j=1;j<=n;j++){

                if(i==j)

                    continue;

                bool flag=true;

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

                    if(port[i][k]==port[j][k]||port[j][k]==2){

                        continue;

                    }

                    flag=false;

                    break;

                }

                if(flag)

                    AddEdge(i,j,INF);

            }

        }

        int ans=Maxflow(s,t);

        vector<node> v;

        for(int i=0;i<edges.size();i+=2){

            if(edges[i].from<=n||edges[i].to>=1+n||edges[i].to==2*n+1||edges[i].from==0)

                continue;

            if(edges[i].flow){

                v.push_back(node{edges[i].from-n,edges[i].to,edges[i].flow});

            }

        }

        cout<<ans<<" "<<v.size()<<endl;

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

            cout<<v[i].from<<" "<<v[i].to<<" "<<v[i].flow<<endl;

        }

    }

    return 0;

}

巴特西

POJ-3436(网络流+最大流+输出路径)

ACM Computer Factory

POJ-3436

这里的输出路径不太理解

最新文章

热门文章