现在的位置: 首页 > 综合 > 正文

POJ 3436 ACM Computer Factory

2014年09月05日 ⁄ 综合 ⁄ 共 2065字 ⁄ 字号 评论关闭

英语不好,直接在网上搜的j嘉哥的题意、、、很详细

题意:电脑工厂有N台机器,每台机器对半成品电脑进行加工。每个电脑由P个部件组成,用0和1表示某部件是否已存在

(1表示存在了)。

每台机器对加工的电脑都是有要求的,只有满足要求,才能进入机器进行加工。

机器对电脑部件的要求用0,1,2表示,输入的P个数中,第i个数为ai,ai=0表示该半成品电脑不能有部件i,ai=1表示

该半成品必须已有部件i(即1),ai=2表示有没有此部件都无关系。

进入机器加工后的电脑出来后所含部件情况用P个数字(0或1)表示。

输入:P和N,接下来N行介绍N个机器,第一个数Q,表示单位时间此机器能加工的电脑数(我是这么理解的),接下来两

个数串,第一个P个数(0,1,2序列)表示该机器的对电脑所含部件的要求,第二个P个数(0,1序列)表示经该机器加工

后,输出的电脑所含部件的情况。

输出:单位时间能生产最多的电脑数,然后输出必须给N台机器间连接的生产线数。每行输出生产线的情况。起点U、终

点V,以及它们的权值W。

以上是嘉哥写的啊,下面我说说:

这个建图有点麻烦啊,得加入超级源点,超级会点啊。。。这个思想以前是没有啊、、以后得记住啊、、每个机器人看做一个接口把满足条件的接口连接在一起、、搜一遍建图啊、、

#include <stdio.h>
#include <string.h>
#include <queue>
#include <iostream>
#define N 200
#define oo 1 << 30

using namespace std;

struct node
{
    int o, in[20], out[20];
}f[N];

int map[N][N], dp[N][N], v[N], link[N], s[N][3], n;

int min(int x, int y)
{
    return x<y?x:y;
}
int EK()
{
    int sum = 0, i, now, min;
    queue<int>q;
    while(1)
    {
        memset(v , 0 , sizeof(v));//竟然把sizeof里面的v写成了0还查了好几个小时啊、、呜呜,手残啊
        memset(link , -1 , sizeof(link));
        while(!q.empty())
            q.pop();
        q.push(0);
        v[0] = 1;
        while(!q.empty())
        {
            now = q.front();
            q.pop();
            if(now == n+1)
                break;
            for(i = 0; i <= n+1; i++)
                if(!v[i] && map[now][i] > 0)
                {
                    link[i] = now;
                    v[i] = 1;
                    q.push(i);
                }
        }
        if(!v[n+1])
            break;
        min = oo;
        for(i = n+1; i != 0; i = link[i])
            if(min > map[link[i]][i])
                min = map[link[i]][i];
        sum += min;
        for(i = n+1; i != 0; i = link[i])
        {
            map[link[i]][i] -= min;//找超级源点
            map[i][link[i]] += min;//找超级汇点
        }
    }
    return sum;
}

int main()
{
    int m, flat, cnt, t, k, i, j;
    while(~scanf("%d %d",&m, &n))
    {
        cnt = 0;
        for(i = 1; i <= n; i++)
        {
            scanf("%d",&f[i].o);
            for(j = 0; j < m; j++)
                scanf("%d",&f[i].in[j]);
            for(j = 0; j < m; j++)
                scanf("%d",&f[i].out[j]);
        }
        memset(map , 0 , sizeof(map));//记录没更新前的值
        for(i = 1; i <= n; i++)
        {
            int flat1 = 1, flat2 = 1;
            for(j = 0; j <  m; j++)
            {
                if(f[i].in[j] == 1)
                    flat1 = 0;
                if(f[i].out[j] == 0)
                    flat2 = 0;
            }
            if(flat1)
                map[0][i] = f[i].o;
            if(flat2)
                map[i][n+1] = f[i].o;
            for(j = 1; j <= n; j++)
            {
                if(i != j)
                {
                    flat = 1;
                    for(k = 0; k < m; k++)
                        if(f[i].out[k]+f[j].in[k] == 1)
                        {
                            flat = 0;
                            break;
                        }
                    if(flat)
                        map[i][j] = min(f[i].o , f[j].o);//用较小的值当做权值,可以满足到可以留到啊。
                }
            }
        }
        memcpy(dp , map , sizeof(map));
        t = EK();
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(dp[i][j] > map[i][j])
                {
                    s[cnt][0] = i;
                    s[cnt][1] = j;
                    s[cnt++][2] = dp[i][j]-map[i][j];//前后可通过的流量的差就是流过的流量
                }
        printf("%d %d\n",t, cnt);
        for(i = 0; i < cnt; i++)
            printf("%d %d %d\n",s[i][0], s[i][1], s[i][2]);
    }
    return 0;
}

抱歉!评论已关闭.