（网络流）ACM Computer Factory --POJ --3436

链接：

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82835#problem/A

题目大意：

一个生产电脑的工厂，有多个机器生产一台电脑，大家都知道一台电脑有多个零部件，这些机器在一个流水线，有些机器工作的前提是需要一些零部件的存在才能继续工作生产，每个机器都有输入设备和输出设备，输入设备意思是根据这几个零部件的存在状态才能使此机器工作，状态包含（0，该零部件不需要存在，1，该零部件必须存在，2，该零部件可有可无）。输出设备意思为该机器工作之后生产的电脑的零部件状态情况（0，没有生产1，生成出该零件）。p，代表每个电脑零部件的个数，m代表几个机器，还给出了每个机器最大的限度能够同时处理机器的个数。根据输入算出最多可以生产的电脑数量和路径个数和路径的详情。

样例说明：
3 4
1号： 15 0 0 0 --> 0 1 0
2号： 10 0 0 0 --> 0 1 1
3号： 30 0 1 2 --> 1 1 1
4号： 3 0 2 1 --> 1 1 1

注意：因为每个生产线的生产能力有限，所以需要拆点，防止超出他的生产能力，比如下图如果不拆点结果就会使20，实际上是10

借鉴别人的代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

#define N 110

#define INF 0x3fffffff

int g[N][N], flow[N], p[N], Line[N][4];

int In[N][20];///输入信息

int backup[N][N]; ///备份图

int nn; ///点的个数，编号0-nn包括源点和汇点

queue<int>q;

int BFS(int Start, int End)

{

    int i, t;

    while(q.size()) q.pop();

    memset(p, -1, sizeof(p));

    p[Start] = 0;

    flow[Start] = INF;///源点可以有无穷的流流进

    q.push(Start);

    while(q.size())

    {

        t = q.front();

        q.pop();

        if(t==End) break;

        ///枚举所有的点，如果点的编号起始点有变化可以改这里

        for(i=0; i<=nn; i++)

        {

            if(i!=Start && p[i]==-1 && g[t][i])

            {

                flow[i] = flow[t] < g[t][i]?flow[t]:g[t][i];

                q.push(i);

                p[i]=t;

            }

        }

    }

    if(p[End]==-1) return -1;  ///找不到汇点上去了，找不到增广路径了

    return flow[End];

}

int Edmonds_Karp(int Start, int End)

{

    int MaxFlow=0;

    int step, now, pre;

    while((step=BFS(Start, End))!=-1)

    {

        MaxFlow += step;

        now = End;

        while(now!=Start)

        {

            pre = p[now];

            g[pre][now] -= step;

            g[now][pre] += step;

            now = pre;

        }

    }

    return MaxFlow;

}

int main()

{

    int p, n, Start, End;

    while(scanf("%d%d", &p, &n)!=EOF)

    {

        memset(g, 0, sizeof(g));

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

        {

            for(int j=0; j<2*p+1; j++)

                scanf("%d", &In[i][j]);

        }

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

            g[2*i-1][2*i] = In[i][0];

        nn = 2*n + 1;

        Start = 0; ///源点

        End = nn;   ///汇点

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

        {

            bool flag_s = true;

            bool flag_t = true;

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

            {

                 if(In[i][j+1]==1) flag_s = false;

                 if(In[i][j+1+p]==0) flag_t = false;

            }

            if(flag_s) g[0][2*i-1] = INF;

            if(flag_t) g[2*i][nn] = INF;

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

                if(i!=j)

                {

                   bool flag = true;

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

                   if((In[i][k+p+1]==0 && In[j][k+1]==1) || (In[i][k+p+1]==1 && In[j][k+1]==0))

                   {

                       flag = false;

                       break;

                   }

                   if(flag) g[2*i][2*j-1] = min(In[i][0], In[j][0]);

                }

        }

        memcpy(backup, g, sizeof(g)); ///先把图备份下来

        printf("%d ", Edmonds_Karp(Start, End));

        int tol=0;

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

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

        {

            if(g[2*i][2*j-1]<backup[2*i][2*j-1])

            {

                Line[tol][0]=i;

                Line[tol][1]=j;

                Line[tol++][2]= backup[2*i][2*j-1] - g[2*i][2*j-1];

            }

        }

        printf("%d\n", tol);

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

            printf("%d %d %d\n", Line[i][0], Line[i][1], Line[i][2]);

    }

    return 0;

}

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

#define N 110

#define INF 0x3fffffff

struct node

{

    int Flow, In[N], Out[N];

}a[N];

int s[N][N], s1[N][N], Layer[N];

int n, p;

/// 重点在建图和拆点， 别的似乎没太多的不同

void Init()

{

    memset(s, , sizeof(s));

    memset(s1, , sizeof(s1));

    memset(Layer, -, sizeof(Layer));

    for(int i=; i<=p; i++)///要把0作为源点， 把n+2作为汇点

    {

        a[].In[i] = ;

        a[].Out[i] = ;

        a[n+].In[i] = ;

        a[n+].Out[i] = ;

    }

    a[].Flow = INF;

    a[n+].Flow = INF;

}

bool CanLink(node n1, node n2)

{

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

    {

        if(n1.Out[i]!=n2.In[i] && n2.In[i]!=)

            return false;

    }

    return true;

}

bool BFS(int Start, int End)

{

    int used[N]={};

    used[Start] = true, Layer[Start] = ;

    queue<int>Q;  Q.push(Start);

    while(Q.size())

    {

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

        if(u==End) return true;

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

        {

            if(s[u][i] && !used[i])

            {

                used[i] = true;

                Layer[i] = Layer[u] + ;

                Q.push(i);

            }

        }

    }

    return false;

}

int DFS(int u, int MaxFlow, int End)

{

    if(u==End) return MaxFlow;

    int uflow = ;

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

    {

        if(Layer[u]+ == Layer[i] && s[u][i])

        {

            int flow = min(s[u][i], MaxFlow-uflow);

            flow = DFS(i, flow, End);

            s[u][i] -= flow;

            s[i][u] += flow;

            uflow += flow;

        }

        if(uflow == MaxFlow)

            break;

    }

    if(uflow==)

        Layer[u] = -;

    return uflow;

}

int Dinic(int Start, int End)

{

    int MaxFlow = ;

    while(BFS(Start, End)==true)

        MaxFlow += DFS(Start, INF, End);

    return MaxFlow;

}

int main()

{

    while(scanf("%d%d", &p, &n)!=EOF)

    {

        int i, j;

        Init();

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

        {

            scanf("%d", &a[i].Flow);

            for(j=; j<=p; j++)

                scanf("%d", &a[i].In[j]);

            for(j=; j<=p; j++)

                scanf("%d", &a[i].Out[j]);

        }

        n+=;

        for(i=; i<=n; i++) /// 拆点并保存原来的路径值, 每个点都要拆分成两个点

        for(j=; j<=n; j++) ///好神奇呀，以前都没遇到过

        {

            if(i==j) ///s1[i+n][j] = s[i+n][j] = a[i].Flow;

                s1[j][i+n] = s[j][i+n] = a[i].Flow;

            else if(i!=j && CanLink(a[i], a[j])==true)

                s1[i+n][j] = s[i+n][j] = a[i].Flow;

        }

        int MaxFlow = Dinic(, n*);

        int k=, x[N], y[N], flow[N];

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

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

        {

            if(s[i+n][j]<s1[i+n][j])

            {

                x[k] = i;

                y[k] = j;

                flow[k++] = s1[i+n][j] - s[i+n][j];

            }

        }

        printf("%d %d\n", MaxFlow, k);

        for(i=; i<k; i++)

            printf("%d %d %d\n", x[i]-, y[i]-, flow[i]);

    }

    return ;

}

巴特西

（网络流）ACM Computer Factory --POJ --3436

最新文章

热门文章